3
$\begingroup$

Given a $n$x$n$ distance matrix of some undirected weighted tree graph, is it possible to infer the underlying tree and its edge weights?

For example, suppose we are given the following distance matrix \begin{pmatrix} 0 & 1 & 4 & 5 & 6 \\ 1 & 0 & 3 & 4 & 5 \\ 4 & 3 & 0 & 1 & 2 \\ 5 & 4 & 1 & 0 & 3 \\ 6 & 5 & 2 & 3 & 0 \end{pmatrix} Assuming strictly positive weights, we know that in each row every minimum corresponds to an edge and its weight, i.e. $1 \leftrightarrow 2$, $3\leftrightarrow 4$ and $3 \leftrightarrow 5$. From there, it's easy to determine that the underlying weighted adjacency graph is given by \begin{pmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 3 & 0 & 0 \\ 0 & 3 & 0 & 1 & 2 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 \end{pmatrix} How to solve this problem in general for strictly positive weights?

$\endgroup$
  • $\begingroup$ This article may be useful : finmath.stanford.edu/~susan/papers/lap.pdf $\endgroup$ – F. C. Feb 14 '17 at 20:46
  • $\begingroup$ By general do you mean that the weights can be negative, or do you just want a procedure for a general tree with non negative weights? I couldn't solve the first one, but the second one is easy. $\endgroup$ – Pushpendre Feb 14 '17 at 22:09
  • $\begingroup$ I meant for strictly positive weigths. I edited the question to clarify this. However, the other problem is also an intersting one. $\endgroup$ – MthQ Feb 15 '17 at 14:19
3
$\begingroup$

The following greedy algorithm should reconstruct the tree corresponding to a given distance matrix $M$, assuming it exists.

Beforehand, one must show that $T$, if it exists, is unique, but unless you insist I will skip these details (informally, you can use induction on $n$: from a tree $T$ for $M$, remove a leaf $l$, use induction to get the unique tree for $M$ with the $l$ row/column removed, then show that there is only one unique place to plug back $l$).

Start with $F$ as the forest on $n$ vertices and no edge.

While $F$ is not a tree:

Choose $u$ and $v$ such that $u$ and $v$ are in two different connected components of $F$ and $M_{u, v}$ is minimum among all possible choices.

Add $uv$ to $F$ and set its weight to $M_{u, v}$

Suppose that we do not obtain a tree with distance matrix $M$ after running the algorithm, but that such a tree $T$ exists.

Let $uv$ be the first inserted (weighted) edge such that $uv$ does not belong to $T$ (observe that if $uv$ belongs to $T$, its weight must be correct). Let $F$ be the forest obtained from the algorithm before inserting $uv$, and for a vertex $x$, denote by $C(x)$ the connected component of $F$ containing $x$. Note that $C(u) \neq C(v)$.

Now, let $z$ be the neighbour of $u$ on the path from $u$ to $v$ in $T$. We have $d(u, v) = d(u, z) + d(v, z)$, implying $d(v, z) < d(u, v)$ (assuming strictly positive weights). If $C(v) \neq C(z)$, the algorithm would have chosen the $vz$ edge instead of $uv$, so assume $C(v) = C(z)$. But then, $C(u) \neq C(z)$ and $d(u, z) < d(u, v)$, again contradicting the choice of the algorithm. Therefore the $uv$ edge is correct.

Of course, there is no guarantee that the algorithm reflects the distances of $M$, but if that's the case, it means that no tree exists for $M$.

$\endgroup$
  • 5
    $\begingroup$ Your algorithm is exactly Kruskal's algorithm for minimum spanning tree. $\endgroup$ – Brendan McKay Feb 15 '17 at 2:27
  • $\begingroup$ One of the comments made me wonder about general weights. Do you easily see any uniqueness issues if we allow for negative weights? $\endgroup$ – MthQ Feb 15 '17 at 14:43
  • $\begingroup$ @BrendanMcKay Indeed, this is Kruskal. So another view of the algorithm is to make a complete graph with edge weights defined by $M$, then run Kruskal on the graph. As a bonus question, would any MST algorithm on this graph reconstruct $T$? $\endgroup$ – Manuel Lafond Feb 15 '17 at 16:08
  • $\begingroup$ @MthQ: yes, there are uniqueness issues. For instance, if all weights are zero, then any tree will do. If zero weights are allowed, but not negative weights, I think the algorithm still works and the proof can be adapted. But with negative weights, I'm not sure. $\endgroup$ – Manuel Lafond Feb 15 '17 at 16:19
  • $\begingroup$ Sorry, I cannot reconstruct the uniqueness proof from your sketch. How do you tell a concrete vertrx is a leaf? OTOH, it seems that the subsequenttext PROVES the uniqueness, since the algorithm indeed determines the traa step by step. $\endgroup$ – Ilya Bogdanov Apr 16 '17 at 6:08

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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