Unique perfect phylogeny is NP-hard
classification
🧬 q-bio.PE
cs.CC
keywords
followingnp-hardaffirmativeanswerchallengecollectiondisplaysgiven
read the original 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 ?"
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.