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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ 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? $\endgroup$– mjqxxxxCommented Jan 19, 2011 at 22:19
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
0
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.
$\begingroup$
$\endgroup$
If the given metric space embeds into a tree metric, the tree must be its 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.
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.
answered Jan 20, 2011 at 4:51
$\begingroup$
$\endgroup$
5
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 for more.
answered Jan 20, 2011 at 4:51
-
$\begingroup$ 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 $\endgroup$ Commented Jan 20, 2011 at 11:40
-
$\begingroup$ 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. $\endgroup$– mjqxxxxCommented Jan 20, 2011 at 17:58
-
$\begingroup$ but then the root-to-leaf distances will not remain constant, which is an ultrametric consequence $\endgroup$ Commented Jan 20, 2011 at 19:43
-
$\begingroup$ 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. $\endgroup$– mjqxxxxCommented Jan 20, 2011 at 19:55
-
$\begingroup$ Yes, that sounds right to me. $\endgroup$ Commented Jan 20, 2011 at 20:37
$\begingroup$
$\endgroup$
3
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)$.
-
1$\begingroup$ 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 $\endgroup$ Commented Jan 19, 2011 at 17:01
-
$\begingroup$ 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 $\endgroup$ Commented Jan 20, 2011 at 4:18
-
$\begingroup$ 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$ $\endgroup$– MikleBCommented Jan 20, 2011 at 9:49