Technical Report Number
Mathematics of Computing
We present a polynomial-time algorithm for determining whether a set of species, described by the characters they exhibit, has a phylogenetic tree, assuming the maximum number of possible states for a character ix fixed. This solves an open problem posed by Kannan and Warnow. Our result should be contrasted with the proof by Steel and Bodlænder, Fellows, and Warnow that the phylogeny problem is NP-complete in general.