DIMACS TR: 93-04

A Polynomial-Time Algorithm for the Phylogeny Problem when the Number of Character States is Fixed

Authors: Richa Agarwala and David Fernandez-Baca


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 is fixed. This solves an open problem posed by Kannan and Warnow. Our result should be contrasted with the proof by Steel and Bodlaender, Fellows, and Warnow that the phylogeny problem is NP-complete in general.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-04.ps
DIMACS Home Page