On the extension of a partial metric to a tree metric

摘要

Farach, Kannan and Warnow (1995) have defined Problem MCA (matrix completion to additive) and proved it to be NP-complete: given a partial dissimilarity d on a finite set X, does there exist a tree metric extending d to all pairs of elements of X. We use a previously described simple method of phylogenetic reconstruction, and its extension to partial dissimilarities, to characterize some classes of polynomial instances of MCA and of a related problem. We point out that these problems admit many other polynomial instances. Our main tool consists of two classes of generalized cycles, together with the corresponding maximal acyclic graphs (2-trees and 2d-trees).