18
$\begingroup$

Suppose $T$ is an constant-degree tree whose structure we do not know. The problem is to output the tree $T$ by asking queries of the form: "Does the node $x$ lie on the path from node $a$ to node $b$?". Assume that each query can be answered in constant time by an oracle. We know the value of $n$, the number of nodes in the tree. The objective is to minimize the time taken to output the tree in terms of $n$.

Does there exist an $o(n^2)$ algorithm for the above problem?

Assume that the degree of any node in $T$ is at most 3.


What I know

Bounded diameter case is easy. If the diameter of the tree is $D$, then we can get a divide-and-conquer algorithm:

Any binary tree has a good separator that divides the tree into components of size no less than 1/3n.

  1. Pick any vertex x. If it is a good separator label that and recurse.
  2. Find all the 3 neighbors of x.
  3. Move in the direction of the neighbor which has the largest number of nodes. Repeat Step 2 with the neighbor.

Since finding the separator takes at most $D$ steps, we get a $O(nD\log n)$ algorithm.

An $O(n\;\log^2 n)$ randomized algorithm. (moved from comments below)

Pick two vertices x and y randomly. With 1/9 probability they will lie on the opposite sides of a separator. Pick the middle node of the path from $x$ to $y$. See if it is a separator, if not do binary search.

It takes $O(n\;\log n)$ expected time to find the separator. So we get a $O(n\;\log^2 n)$ randomized algorithm.


Background. I learnt about this problem from a friend who works in probabilistic graphical models. The above problem roughly corresponds to learning the structure of a junction tree using an oracle which, given three random variables X,Y and Z, can tell the value of mutual information between X and Y given the value of Z. If the value is close to zero, we may assume that Z lies on the path from X to Y.

$\endgroup$
  • 7
    $\begingroup$ Please reveal what you already know about the problem, so we don't waste our time reinventing the wheel. $\endgroup$ – Jeffε Mar 19 '12 at 15:54
  • $\begingroup$ @JɛffE I've edited my question. $\endgroup$ – Jagadish Mar 19 '12 at 18:17
5
$\begingroup$

No. The following simple adversary strategy implies that any algorithm to reconstruct an $n$-node tree requires at least $\binom{n-1}{2} = n(n-1)/2$ "betweenness" queries.

Arbitrarily label the nodes $0,1,2,\dots,n-1$. The adversary answers all queries as though the tree is a star with vertex $0$ in the center; think of $0$ as the root and the other nodes as its children.

Between?(a,x,b)
    if x=0 return TRUE else return FALSE

Now suppose the algorithm halts after performing less than $n(n-1)/2$ queries. Then there must be two vertices $y$ and $z$, neither equal to zero, such that the algorithm has not queried any permutation of the triple $(0,y,z)$. If the algorithm claims that the tree is not a star with center $0$, the adversary reveals its input, proving the algorithm wrong. The adversary then reveals that $x$ is actually the only child of $y$, proving the algorithm wrong again.

Update: Oops, just noticed the degree constraint. Fortunately, this is not a major hurdle. Replace node $0$ with your favorite binary tree, with the other $n-1$ nodes as leaves in some unknown order, and then reveal this subtree to the reconstruction algorithm. Reconstructing the resulting $(2n-3)$-node binary tree still requires at least $n(n-1)/2$ queries. Equivalently, reconstructing an $m$-node binary tree requires at least $(m+3)(m+2)/8$ queries. (I'm sure a more subtle construction would improve the constant.) As Jagadish points out, this generalization doesn't work; queries about internal nodes in the tree impose an ordering on the leaves, which reduced the number of necessary queries.

$\endgroup$
  • $\begingroup$ My question is about constant-degree trees. This argument doesn't work for that case, right? $\endgroup$ – Jagadish Mar 19 '12 at 14:53
  • 2
    $\begingroup$ @Jagadish: (1) I do not think that this proof of a lower bound works for randomized algorithms. The adversary can still construct a failing example, but that does not contradict the hypothesis that the randomized algorithm works correctly with high probability. (2) By the way, it seems that you asked the question knowing the answer. What did you do that for? $\endgroup$ – Tsuyoshi Ito Mar 19 '12 at 15:37
  • 2
    $\begingroup$ I see. Thanks for the explanation, and also thanks for editing the question! $\endgroup$ – Tsuyoshi Ito Mar 19 '12 at 19:41
  • 4
    $\begingroup$ If you have a randomized algorithm, then you have an algorithm. Determinism is overrated. $\endgroup$ – Jeffε Mar 20 '12 at 8:54
  • 1
    $\begingroup$ This problem reminds me of sorting/matching nuts and bolts. A randomized algorithm that runs in $O(n \log n)$ time with high probability is easy — it's just randomized quicksort. There is a deterministic $O(n\log n)$-time algorithm, but it is seriously nontrivial. $\endgroup$ – Jeffε Mar 21 '12 at 8:28
5
$\begingroup$

Anindya Sen and I have a paper in ALT '13 where we give an $\tilde O(n \sqrt{n})$ algorithm for this problem. We don't know if a better algorithm is possible.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.