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.
- Pick any vertex x. If it is a good separator label that and recurse.
- Find all the 3 neighbors of x.
- 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.