Sub-linear algorithm for minimum spanning tree (MST) for a tree metric. - MathOverflow

Sub-linear algorithm for minimum spanning tree (MST) for a tree metric.

2011-11-09T21:02:20Z

Lets $T=(V,E,W)$ be a weighted tree (undirected acyclic graph) with positive weights on $n$ nodes. The weights define a natural metric on the set $V$ : $d(i,j) = $ weight of the (unique) path between $i$ and $j$ in $T$.

Now, lets suppose that $T$ is unknown and that we have access only to the $n\times n$ distance matrix induced by the tree. My question is : Can one learn the structure of $T$ without looking at all the ${n\choose 2}$ distances?

Alternatively, it is easy to see that the tree $T$ is the MST of the complete graph on $V$ with weights given by $d(\cdot,\cdot)$. Is there a sub-linear algorithm for finding the MST of this special, completely connected graph?

Edit: I must add that I would be happy to restrict attention to certain families of trees. For instance, this can be done when the tree $T$ is a line graph and if we know this before hand.

Answer by Brendan McKay for Sub-linear algorithm for minimum spanning tree (MST) for a tree metric.

2011-11-10T00:41:57Z

Lev Reyzin and Nikhil Srivastava, On the longest path algorithm for reconstructing trees from distance matrices. Inform. Process. Lett. 101 (2007), no. 3, 98–100.

I haven't looked at this, but the abstract indicates it is where you need to look for information and references.

Answer by David Eppstein for Sub-linear algorithm for minimum spanning tree (MST) for a tree metric.

2011-11-10T07:44:20Z

Let $T$ be a star with weights 1, 2, 3, 4, ... on its edges. Then unless you test the distance between every two leaves of $T$ you can't distinguish it from a different tree where some two leaves whose distance wasn't tested belong to a single path from the hub of the star. So there's an $\Omega(n^2)$ lower bound for this problem, matching the upper bound.