A Polynomial-Time Algorithm For the Perfect Phylogeny Problem When the Number of Character States is Fixed
Richa Agarwala, David Fernández‐Baca · SIAM Journal on Computing · 1994
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–1161 and Bodlaender, Fellows, and Warnow [Proceedings of the 19th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science, 1992, pp. 273–2831 that the perfect phylogeny problem is NP complete in general.