Optimal 2/3 halfing in interactive tree problems

Правка en5, от maomao90, 2023-09-16 09:35:33

It is not uncommon to have interactive tree problems where you are allowed to query some connected component of the tree and use the return value to determine whether the answer is in the connected component or outside the connected component (Link to example problem). The general approach for these kinds of problems is to always choose a connected component of size $$$\frac{N}{2}$$$. However, there are also problems where the allowed queries are more restricted, preventing $$$\frac{N}{2}$$$ halving from being possible. This blog covers one of those types of problems.

Definitions

  • Subtree: $$$S(r, u)$$$ contains the set of vertices in the subtree of vertex $$$u$$$ if the tree was rooted at vertex $$$r$$$.
  • Neighbour: $$$N(u)$$$ contains the set of vertices that are directly adjacent to vertex $$$u$$$.
  • Extended subtree: $$$ES(r, V) = \bigcup_{v\in V} S(r, v)\text{ if } v\in N(r)$$$. In other words, an extended subtree is a combination of the subtrees of a chosen set of vertices that are directly adjacent to the root.

Problem Structure

There is a hidden special vertex in a tree with $$$n$$$ vertices. Find the special vertex using at most $$$\left\lceil\log_{1.5}n\right\rceil$$$ of the following query:

  • Choose an extended subtree of the tree. The grader will return whether the special vertex is in the chosen extended subtree. More formally, choose any vertex $$$r$$$ and a subset of neighbours $$$V \subseteq N(r)$$$, then the grader will return whether the special vertex $$$x \in ES(r, V)$$$.

Solution

Let us denote the size of the chosen extended subtree as $$$x$$$. If the grader returns that the special vertex is in the extended subtree, we can combine the root together with the extended subtree to form a new tree with $$$x + 1$$$ vertices. Otherwise, the vertices outside of the extended subtree form a tree with $$$n - x$$$ vertices. This means that with each query, we can reduce the size of the tree to at least $$$\max(x + 1, n - x)$$$.

Since we are allowed to use $$$\left\lceil\log_{1.5}n\right\rceil$$$ queries, we will be able to solve this problem if the size of the tree reduces to at least $$$\frac{2n}{3}$$$ after each query. Solving the inequality $$$\max(x + 1, n - x) \le \frac{2n}{3}$$$, we get $$$\frac{n}{3} \le x \le \frac{2n}{3} - 1$$$. Now, let us see whether it is always possible to find an extended subtree of size between $$$\frac{n}{3}$$$ and $$$\frac{2n}{3} - 1$$$.

Let us root the tree at its centroid. Recall that the all the children of the centroid have subtree sizes less than or equal to $$$\frac{n}{2}$$$. If there exist a child with subtree size more than or equal to $$$\frac{n}{3}$$$, then that lone subtree can be the chosen extended subtree since $$$\frac{n}{3} \le x \le \frac{n}{2} \le \frac{2n}{3} - 1$$$.

Теги interactive, tree, centroid

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский maomao90 2023-09-17 07:22:15 76 Tiny change: ' but with uneven chains to come ' -> ' but with different chain lengths to come ' (published)
en8 Английский maomao90 2023-09-17 07:10:28 6461 Tiny change: 'e form: $k x_1 x_2 \ldots x_' -> 'e form: $k\, x_1\, x_2\, \ldots x_'
en7 Английский maomao90 2023-09-16 19:01:12 60
en6 Английский maomao90 2023-09-16 18:59:15 2623
en5 Английский maomao90 2023-09-16 09:35:33 474
en4 Английский maomao90 2023-09-16 09:25:12 4 Tiny change: ' the tree by at least ' -> ' the tree to at least '
en3 Английский maomao90 2023-09-16 09:24:18 293
en2 Английский maomao90 2023-09-16 09:13:50 527
en1 Английский maomao90 2023-09-16 07:28:39 1674 Initial revision (saved to drafts)