Reconstructing a tree from separator queries

Question

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.

Answer 1

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.

Answer 2

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.