On the extension of a partial metric to a tree metric Original Research Article

Farach et al. (Algorithmica 13 (1995) 155–179) 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. We focus particularly on two classes of generalized cycles, together with the corresponding maximal acyclic graphs (2-trees and 2d-trees).