Two strikes against perfect phylogeny

Hans L. Bodlaender, Mike R. Fellows, Tandy J. Warnow

Research output: Chapter in Book/Report/Conference proceedingConference contribution


One of the major efforts in molecular biology is the computation of phylogenies for species sets. A longstanding open problem in this area is called the Perfect Phylogeny problem. For almost two decades the complexity of this problem remained open, with progress limited to polynomial time algorithms for a few special cases, and many relaxations of the problem shown to be NP-Complete. From an applications point of view, the problem is of interest both in its general form, where the number of characters may vary, and in its fixed-parameter form. The Perfect Phylogeny problem has been shown to be equivalent to the problem of triangulating colored graphs[30]. It has also been shown recently that for a given fixed number of characters the yes-instances have bounded treewidth[45], opening the possibility of applying methodologies for bounded treewidth to the fixed-parameter form of the problem. We show that the Perfect Phylogeny problem is difficult in two different ways. We show that the general problem is NP-Complete, and we show that the various finite-state approaches for bounded treewidth cannot be applied to the fixed-parameter forms of the problem.

Original languageEnglish (US)
Title of host publicationAutomata, Languages and Programming - 19th International Colloquium, Proceedings
EditorsWerner Kuich
Number of pages11
ISBN (Print)9783540557197
StatePublished - 1992
Externally publishedYes
Event19th International Colloquium on Automata, Languages, and Programming, ICALP 1992 - Wien, Austria
Duration: Jul 13 1992Jul 17 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume623 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Colloquium on Automata, Languages, and Programming, ICALP 1992

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Two strikes against perfect phylogeny'. Together they form a unique fingerprint.

Cite this