Sub-linear algorithm for minimum spanning tree (MST) for a tree metric. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T05:22:52Z http://mathoverflow.net/feeds/question/80522 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80522/sub-linear-algorithm-for-minimum-spanning-tree-mst-for-a-tree-metric Sub-linear algorithm for minimum spanning tree (MST) for a tree metric. Bhakt 2011-11-09T21:02:20Z 2011-11-10T07:44:20Z <p>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$.</p> <p>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? </p> <p>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? </p> <p>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. </p> http://mathoverflow.net/questions/80522/sub-linear-algorithm-for-minimum-spanning-tree-mst-for-a-tree-metric/80539#80539 Answer by Brendan McKay for Sub-linear algorithm for minimum spanning tree (MST) for a tree metric. Brendan McKay 2011-11-10T00:41:57Z 2011-11-10T00:41:57Z <p>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.</p> <p>I haven't looked at this, but the abstract indicates it is where you need to look for information and references. </p> http://mathoverflow.net/questions/80522/sub-linear-algorithm-for-minimum-spanning-tree-mst-for-a-tree-metric/80566#80566 Answer by David Eppstein for Sub-linear algorithm for minimum spanning tree (MST) for a tree metric. David Eppstein 2011-11-10T07:44:20Z 2011-11-10T07:44:20Z <p>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.</p>