Reconstructing Metric Trees from Order Information on Triples is NP Complete

2006/03/04 by Eric Babson, Babson, Eric
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.math/0603116

arxiv created 2006/03/04 · arxiv updated 2009/12/01

Abstract

We show that reconstructing a tree from order information on triples is NP-hard. This is in contrast to the case for ultra-metrics and for subtree information on quadruples which are both known to allow polynomial time reconstruction.

Related

• Optimal Algorithm to Reconstruct a Tree from a Subtree Distance
• Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant
• Deciding the Closure of Inconsistent Rooted Triples is NP-Complete
• Reconstructing Trees from Subtree Weights
• Affine and Projective Tree Metric Theorems