Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
probably no (I recall reading some lower bound involving average degree of a vertex in a graph) –  Suvrit Nov 9 '11 at 21:05
    
What structure of T do you want to learn about? –  Michael Biro Nov 9 '11 at 21:10
    
By structure, I mean I want to learn T. That is, the edge set. –  Bhakt Nov 9 '11 at 21:14
1  
The path lengths don't define a tree uniquely if you allow zero weight edges. Do they define a unique tree if all edge weights are positive? –  Michael Biro Nov 9 '11 at 22:15
    
@Michael : Sorry, the edge-weights have to be positive. (Edited question to reflect this). In this case, the path-lengths do define a unique (minimum spanning) tree. This can be proved without too much effort by contradiction. [For instance, see the (famous) paper by "Approximating Discrete Probability Distributions with Dependence Trees" Chow and Liu (1968)] –  Bhakt Nov 9 '11 at 23:13
show 3 more comments

2 Answers

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.

share|improve this answer
    
I agree. This is one of the reasons I added an edit that said I am happy to look at restricted families of graphs (bounded degree, e.g.). Here is a trivial example : If I restrict my attention to only line graphs, then $\Theta(n)$ measurements suffice to identify which line graph is the right one. So, the real question is : Are there interesting (non-trivial) assumptions one can make about the underlying tree that "generates" distances so that $o(n^2)$ measurements suffice to identify it? I like your example. Thanks a lot for your answer! –  Bhakt Nov 11 '11 at 18:17
    
@David, I think that's not quite right. If you find the center of the star, you can first make sure it is as star... etc. The easiest way I know of making the $O(n^2)$ lower bound work is using "two-level" stars. See Proposition 7 of this cc.gatech.edu/~lreyzin/papers/ReyzinSri07_alt.pdf –  Lev Reyzin Jan 5 '12 at 23:02
    
When you say "first make sure it is a star", what do you mean? The two different trees in my answer do not differ from each other in the distances of the leaves from the hub, only in their distances from each other. –  David Eppstein Jan 10 '12 at 7:25
    
Sorry, I misread your answer -- I missed that the numbers are weights (I thought they were just labels). The two-level star is needed only in the unweighted case. –  Lev Reyzin Jan 10 '12 at 14:14
add comment

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.

share|improve this answer
    
Thanks! This seems very relevant. –  Bhakt Nov 10 '11 at 5:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.