<p>Bioinformatics people seem to know an $O(n^2)$-time (and hence linear-time) algorithm in the context of the reconstruction of phylogenetic trees based on distance matrices.  Please look at Pages 27-34 of the slides available at <a href="http://www.cs.lth.se/home/Andrzej_Lingas/PhylogeneticTrees.pdf" rel="nofollow">http://www.cs.lth.se/home/Andrzej_Lingas/PhylogeneticTrees.pdf</a>.  </p>

CC BY-SA 2.5
2011-01-20T04:29:00.123Z
2011-01-20T04:29:00.123Z
Yoshio Okamoto
<p>If the given metric space embeds into a tree metric, the tree must be its <a href="http://en.wikipedia.org/wiki/Tight_span" rel="nofollow">tight span</a>. The O(n^2) time algorithms referred to in Yoshio's answer can be extended to certain two-dimensional tight spans: see <a href="http://arxiv.org/abs/0909.1866" rel="nofollow">arXiv:0909.1866</a>.</p>

<p>One method for solving the problem is incremental (as in the linked preprint, but much simpler): maintain a tree T containing the first i points from your metric space (that is, having the same distances as the corresponding entries of your input distance matrix) and extend it one point at a time; at each step there's at most one way to extend it.</p>

<p>To test whether to attach your new point r along edge uv of your existing tree, find points p and q of your metric space that are on opposite sides of edge uv. The new point attaches to a point inside edge uv iff d(p,r) > d(p,u) and d(q,r) > d(q,v); using this test on each of the edges of the existing tree, you can find where it attaches in O(n) time. Once you've found where to attach it you can test in O(n) time whether the distances to all the other points are correct. So each point you add takes time O(n) and the whole algorithm takes time O(n^2), optimal since that's the size of your input distance matrix.</p>

CC BY-SA 2.5
2011-01-20T04:51:27.810Z
2011-01-20T04:51:27.810Z
David Eppstein
<p>There's a little bit of confusion that has been introduced into the question by Christoph's comment (and mjqxxxx's comment on the question reflects that). If you just want to map the nodes of X into a weighted tree endowed with the shortest path metric (as the question states), then you're asking about testing whether a metric is a tree metric. I don't know whether this can be done faster than using the 4-point condition.</p>

<p>However, if as Christoph's comment indicates, you want to consider embeddings in which the vertices are leaves, then you're asking (sort of) if the metric is an ultrametric. Ultrametrics are a little stronger, because the root-to-leaf distance for ALL nodes is the same, but it's also easier to verify whether a metric is an ultrametric via the MST. See <a href="http://www.cs.cmu.edu/~anupamg/metrics/lectures/lec12.ps" rel="nofollow">Anupam Gupta's notes</a> for more. </p>

CC BY-SA 2.5
2011-01-20T11:40:03.317Z
Perhaps my example was a bit confusing as it was not only a tree metric but also an ultrametric... Indeed I was looking for algorithm for testing if a metric is a tree metric
Christoph
CC BY-SA 2.5
2011-01-20T17:58:16.420Z
I don't see how requiring the vertices to map to leaves, or requiring the tree to be rooted and binary, makes a difference.  If a vertex maps to an internal node of the tree, then that vertex can equally well map to a (new) leaf node connected to that internal node by an edge with weight 0.  Similarly, if a node has degree $k>2$, it can be split into $k-1$ binary nodes that form a subtree all of whose edges have weight 0.  Finally, if the tree is unrooted, a (new) root node can be placed at the center of an arbitrary edge.
mjqxxxx
CC BY-SA 2.5
2011-01-20T19:43:10.560Z
but then the root-to-leaf distances will not remain constant, which is an ultrametric consequence
Suresh Venkat
CC BY-SA 2.5
2011-01-20T19:55:38.397Z
Christoph has confirmed that his question is asking about tree metrics, not ultrametrics.  My assertion is that a metric on an $n$-point space is a tree metric iff there is an isometric mapping of the $n$ points to the $n$ leaf nodes of a rooted, weighted, binary tree equipped with the shortest path metric.
mjqxxxx
CC BY-SA 2.5
2011-01-20T20:37:46.033Z
Yes, that sounds right to me.
Suresh Venkat
CC BY-SA 2.5
2011-01-20T04:51:37.403Z
2011-01-20T04:51:37.403Z
Suresh Venkat
<p>If it is tree metric then MST of the distance graph will be the suitable tree. To see this just run Kruskal's algorithm.</p>

<p>EDIT:
Here is a draft of $O(n^2)$ algorithm. Initialy we have distance graph $G(V,E)$, where $V$ is the input point set and $E = V\times V$.  Suppose we have two leaves of the tree $v$ and $u$. We can find closest to $v$ vertex $w$ in the tree (adjacent vertex) in $O(n)$ time. This vertex may not be in input points set. After finding $w$ if it is a new vertex we add $w$ in the graph and calulate distances from every graph vertex to $w$ (if $w$ is a new vertex) and then we remove $v$ from the graph. In the same time we can find new leaf instead $v$ in $O(n)$. Thus for each tree leaf we will spend $O(n)$.</p>

CC BY-SA 2.5
2011-01-19T17:01:45.053Z
The embedding in the problem does not need to be surjective: E.g. the metric induced by $K_n$ with unit edge weight is a tree metric as it embeds into  $K_{1,n}$ with edge weight $1/2$ with the vertices embedded into the leaves
Christoph
CC BY-SA 2.5
2011-01-20T04:18:33.713Z
I'm not sure the update makes sense. What does it mean for a vertex "not to be in the input points set" ? All you are given is a distance matrix
Suresh Venkat
CC BY-SA 2.5
2011-01-20T09:49:30.370Z
Closest $w$ point to the leaf $v$ may be new vertex if $d(v,w) < d(v, p),\forall p \in V$. To find closets vertex you need just find $d(v,w) = \min_{p\in V}{(d(v,p)+d(v,u)-d(p,u))}/2$
MikleB
CC BY-SA 2.5
2011-01-19T16:06:42.837Z
2011-01-19T22:26:43.273Z
2011-01-19T22:26:43.273Z
MikleB
<p>An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, i.e. a metric is a tree metric iff every 4 point subspace is a tree metric. In particular this implies that one can decide in polynomial time whether a given metric is a tree metric by examining all quadruples of points in the space.<br>
My question now is what other (than the trivial) algorithms are there? Can one check in linear (in the number of points) time whether a metric is a tree metric?</p>

CC BY-SA 2.5
2011-01-19T22:19:01.750Z
For clarity: the tree in which the original $n$ points can be isometrically embedded generally must have more than $n$ points.  I believe you can assume with no loss of generality that it is a rooted binary tree with $n-1$ internal nodes and $n$ leaf nodes, with non-negative edge weights, and that the embedding maps the original $n$ points to the leaf nodes.  Is that correct?
mjqxxxx
<ds.algorithms><reference-request><metrics>
Deciding whether a metric is a tree metric
Christoph
# Deciding whether a metric is a tree metric

(Asked by: username_0 on 2011-01-19)

An n-point metric space is a tree metric if it isometrically embeds into the shortest path metric of a tree (with nonnegative edge weights). Tree metrics can be characterized by the 4 point property, i.e. a metric is a tree metric iff every 4 point subspace is a tree metric. In particular this implies that one can decide in polynomial time whether a given metric is a tree metric by examining all quadruples of points in the space.  
My question now is what other (than the trivial) algorithms are there? Can one check in linear (in the number of points) time whether a metric is a tree metric?

**Tags:** ds.algorithms, reference-request, metrics
> **Comments:**
> **username_1**: For clarity: the tree in which the original $n$ points can be isometrically embedded generally must have more than $n$ points.  I believe you can assume with no loss of generality that it is a rooted binary tree with $n-1$ internal nodes and $n$ leaf nodes, with non-negative edge weights, and that the embedding maps the original $n$ points to the leaf nodes.  Is that correct?  

---

## 4 answers

### Answer by username_2 on 2011-01-20. Score: 2 | Accepted answer

Bioinformatics people seem to know an $O(n^2)$-time (and hence linear-time) algorithm in the context of the reconstruction of phylogenetic trees based on distance matrices. Please look at Pages 27-34 of the slides available at <http://www.cs.lth.se/home/Andrzej_Lingas/PhylogeneticTrees.pdf>.


---

### Answer by username_3 on 2011-01-20. Score: 4

If the given metric space embeds into a tree metric, the tree must be its [tight span](http://en.wikipedia.org/wiki/Tight_span). The O(n^2) time algorithms referred to in Yoshio's answer can be extended to certain two-dimensional tight spans: see [arXiv:0909.1866](http://arxiv.org/abs/0909.1866).

One method for solving the problem is incremental (as in the linked preprint, but much simpler): maintain a tree T containing the first i points from your metric space (that is, having the same distances as the corresponding entries of your input distance matrix) and extend it one point at a time; at each step there's at most one way to extend it.

To test whether to attach your new point r along edge uv of your existing tree, find points p and q of your metric space that are on opposite sides of edge uv. The new point attaches to a point inside edge uv iff d(p,r) > d(p,u) and d(q,r) > d(q,v); using this test on each of the edges of the existing tree, you can find where it attaches in O(n) time. Once you've found where to attach it you can test in O(n) time whether the distances to all the other points are correct. So each point you add takes time O(n) and the whole algorithm takes time O(n^2), optimal since that's the size of your input distance matrix.


---

### Answer by username_4 on 2011-01-20. Score: 1

There's a little bit of confusion that has been introduced into the question by Christoph's comment (and mjqxxxx's comment on the question reflects that). If you just want to map the nodes of X into a weighted tree endowed with the shortest path metric (as the question states), then you're asking about testing whether a metric is a tree metric. I don't know whether this can be done faster than using the 4-point condition.

However, if as Christoph's comment indicates, you want to consider embeddings in which the vertices are leaves, then you're asking (sort of) if the metric is an ultrametric. Ultrametrics are a little stronger, because the root-to-leaf distance for ALL nodes is the same, but it's also easier to verify whether a metric is an ultrametric via the MST. See [Anupam Gupta's notes](http://www.cs.cmu.edu/~anupamg/metrics/lectures/lec12.ps) for more.

> **Comments:**
> **username_0**: Perhaps my example was a bit confusing as it was not only a tree metric but also an ultrametric... Indeed I was looking for algorithm for testing if a metric is a tree metric  
> **username_1**: I don't see how requiring the vertices to map to leaves, or requiring the tree to be rooted and binary, makes a difference.  If a vertex maps to an internal node of the tree, then that vertex can equally well map to a (new) leaf node connected to that internal node by an edge with weight 0.  Similarly, if a node has degree $k>2$, it can be split into $k-1$ binary nodes that form a subtree all of whose edges have weight 0.  Finally, if the tree is unrooted, a (new) root node can be placed at the center of an arbitrary edge.  
> **username_4**: but then the root-to-leaf distances will not remain constant, which is an ultrametric consequence  
> **username_1**: Christoph has confirmed that his question is asking about tree metrics, not ultrametrics.  My assertion is that a metric on an $n$-point space is a tree metric iff there is an isometric mapping of the $n$ points to the $n$ leaf nodes of a rooted, weighted, binary tree equipped with the shortest path metric.  
> **username_4**: Yes, that sounds right to me.  

---

### Answer by username_5 on 2011-01-19. Score: 0

If it is tree metric then MST of the distance graph will be the suitable tree. To see this just run Kruskal's algorithm.

EDIT:
Here is a draft of $O(n^2)$ algorithm. Initialy we have distance graph $G(V,E)$, where $V$ is the input point set and $E = V\times V$. Suppose we have two leaves of the tree $v$ and $u$. We can find closest to $v$ vertex $w$ in the tree (adjacent vertex) in $O(n)$ time. This vertex may not be in input points set. After finding $w$ if it is a new vertex we add $w$ in the graph and calulate distances from every graph vertex to $w$ (if $w$ is a new vertex) and then we remove $v$ from the graph. In the same time we can find new leaf instead $v$ in $O(n)$. Thus for each tree leaf we will spend $O(n)$.

> **Comments:**
> **username_0**: The embedding in the problem does not need to be surjective: E.g. the metric induced by $K_n$ with unit edge weight is a tree metric as it embeds into  $K_{1,n}$ with edge weight $1/2$ with the vertices embedded into the leaves  
> **username_4**: I'm not sure the update makes sense. What does it mean for a vertex "not to be in the input points set" ? All you are given is a distance matrix  
> **username_5**: Closest $w$ point to the leaf $v$ may be new vertex if $d(v,w) < d(v, p),\forall p \in V$. To find closets vertex you need just find $d(v,w) = \min_{p\in V}{(d(v,p)+d(v,u)-d(p,u))}/2$  

---

