Unique perfect phylogeny is NP-hard

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 ?"

References in corpus (1)

• Generalizing the Splits Equivalence Theorem and Four Gamete Condition: Perfect Phylogeny on Three State Characters