An algorithm for finding a representation of a subtree distance

Generalizing the concept of tree metric, Hirai (Ann Combinatorics 10:111–128, 2006) introduced the concept of subtree distance. A nonnegative-valued mapping \(d:X\times X \rightarrow \mathbb {R}_+\) is called a subtree distance if there exist a weighted tree T and a family \(\{T_x\mid x \in X\}\) of subtrees of T indexed by the elements in X such that \(d(x,y)=d_T(T_x,T_y)\), where \(d_T(T_x,T_y)\ge 0\) is the distance between \(T_x\) and \(T_y\) in T. Hirai (2006) provided a characterization of subtree distances that corresponds to Buneman’s (J Comb Theory, Series B 17:48–50, 1974) four-point condition for tree metrics. Using this characterization, we can decide whether or not a given mapping is a subtree distance in O\((n^4)\) time. In this paper, we show an O\((n^3)\) time algorithm that finds a representation of a given subtree distance. This results in an O\((n^3)\) time algorithm for deciding whether a given mapping is a subtree distance.

The authors are grateful to Professor Hiroshi Hirai for useful suggestions for the design of the algorithm presented in this paper. Thanks are also due to the anonymous referees for their helpful suggestions, which improved readability of the paper and simplified the proofs of Lemmas 1, 2 and Proposition 3. This work was supported by JSPS KAKENHI Grant Number 15K00033.

Authors and Affiliations

1. Faculty of Engineering, Shizuoka University, Johoku 3-5-1, Hamamatsu, 432-8561, Japan

   Kazutoshi Ando

2. DAITO GIKEN, INC., Chuo-ku Kyobashi 3-1-1, Tokyo, 104-0031, Japan

   Koki Sato

Corresponding author

Correspondence to Kazutoshi Ando.

Reprints and permissions