3
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ probably no (I recall reading some lower bound involving average degree of a vertex in a graph) $\endgroup$
    – Suvrit
    Commented Nov 9, 2011 at 21:05
  • $\begingroup$ What structure of T do you want to learn about? $\endgroup$
    – Michael Biro
    Commented Nov 9, 2011 at 21:10
  • $\begingroup$ By structure, I mean I want to learn T. That is, the edge set. $\endgroup$
    – Bhakt
    Commented Nov 9, 2011 at 21:14
  • 1
    $\begingroup$ 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? $\endgroup$
    – Michael Biro
    Commented Nov 9, 2011 at 22:15
  • $\begingroup$ @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)] $\endgroup$
    – Bhakt
    Commented Nov 9, 2011 at 23:13

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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! $\endgroup$
    – Bhakt
    Commented Nov 11, 2011 at 18:17
  • $\begingroup$ @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 $\endgroup$
    – Lev Reyzin
    Commented Jan 5, 2012 at 23:02
  • $\begingroup$ 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. $\endgroup$
    – David Eppstein
    Commented Jan 10, 2012 at 7:25
  • $\begingroup$ 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. $\endgroup$
    – Lev Reyzin
    Commented Jan 10, 2012 at 14:14
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .