Unique perfect phylogeny is NP-hard
classification
🧬 q-bio.PE
cs.CC
keywords
followingnp-hardaffirmativeanswerchallengecollectiondisplaysgiven
Add this Pith Number to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{5N6ADMBW}
Prints a linked pith:5N6ADMBW badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
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.