Unique perfect phylogeny is NP-hard

2010/11/26 by Michel Habib, Habib, Michel, Juraj Stacho +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Graph Theory Research #Algorithms and Data Compression #Computational Complexity (cs.CC) #FOS: Biological sciences #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Populations and Evolution (q-bio.PE) #cs.CC #q-bio.PE

paper · pdf · doi:10.48550/arxiv.1011.5737

arxiv created 2010/11/26 · openalex publication_date 2010/11/26 · arxiv updated 2010/11/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We answer, in the affirmative, the following question proposed by Mike Steel as a 100 challenge: "Is the following problem NP-hard? Given a ternary phylogenetic X-tree T and a collection Q of quartet subtrees on X, is T the only tree that displays Q ?"

Related

• Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks
• Unique Perfect Phylogeny Characterizations via Uniquely Representable Chordal Graphs
• Capturing a phylogenetic tree when the number of character states varies with the number of leaves
• The Complexity of Finding Multiple Solutions to Betweenness and Quartet Compatibility
• Slim Sets of Binary Trees