A POLYNOMIAL-TIME ALGORITHM FOR THE PERFECT PHYLOGENY PROBLEM WHEN THE NUMBER OF CHARACTER STATES IS FIXED

This paper presents a polynomial-time algorithm for determining whether a set of species, described by the characters they exhibit, has a perfect phylogeny, assuming the maximum number of possible states for a character is fixed. This solves a longstanding open problem. This result should be contrasted with the proof by Steel [J. Classification 9(1992), pp.91-116] and Bodlaender, Fellows, and Warnow [Proceedings of the 19th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 1992. pp.273-283] that the perfect phylogeny problem is NP complete in general.