Optimal online algorithm to guess the tree

Question

I have a tree on $n$ vertices. Your goal is to find the adjacency list for it.

$n$ is known to you from the start. You can pick a vertex and ask for the lengths of the shortests paths from it to the other $n-1$ vertices (i.e. you input an integer $1\leq i \leq n$ and get $n-1$ integers $1\leq d \leq n-1$). The lengths are listed in the order consistent with the enumeration of the vertices.

What is the algorithm using as few queries as possible (without making any additional assumptions about the tree)?

After the first query you can bipartition of the tree by the parity of the shortest path so $\lceil \frac{n}{2} \rceil$ queries are always sufficient. An algorithm that keeps adapting after each query might do better.

Answer 1

You may indeed find some improvements, like :

• never query on a vertex, you know to be a leaf.
• guess some distant edges.

But this does not change the worst case for a totally unknown tree which is indeed $n/2$ as you guessed. Just imagine this tree:

• one root vertex with edges to $N$ other vertices.
• each of these $N$ vertices has one (and only one) additional edge to a leaf vertex. this tree has a $2 \times N + 1$ vertices.

And even if you identify quickly the pattern, you still have to query once per "branch", thus $N$ times.