## 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

**
ABSTRACT
**

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