Computational complexity of inferring phylogenies by compatibility

Abstract.—A well-known approach to inferring phylogenies involves finding a phylogeny with the largest number of characters that are perfectly compatible with it. Variations of this problem depend on whether characters are: cladistic (rooted) or qualitative (unrooted); binary (two states) or unconstrained (more than one state). The computational cost of known algorithms that guarantee solutions to these problems increases at least exponentially with problem size; practical computational considerations restrict the use of such algorithms to analyzing problems of small size. We establish that the four basic variants of the compatibility problem are all NP-complete and, thus, are so difficult computationally that for them efficient optimal algorithms are not likely to exist. [Character compatibility; computational complexity; evolutionary tree; NP-complete; phylogenetic inference.] Resume.—Une approche bien connue a l'etude de revolution des especes est basee sur la recherche de l'arbre phylogenetique avec lequel il y a un nombre maximal de caracteres com-patibles. Des variantes de ce probleme impliquent des caracteres soit cladistiques (avec racine), soit qualitatifs (sans racine); des caracteres soit binaires (deux valeurs), soit sans contrainte (plus qu'une valeur). Les algorithmes connus pour resoudre ces problemes exigent un temps d'ordi