Communications in Information and Systems

Volume 9 (2009)

Number 4

The Three-state Perfect Phylogeny Problem Reduces to 2-SAT

Pages: 295 – 302

DOI: http://dx.doi.org/10.4310/CIS.2009.v9.n4.a1

Authors

Dan Gusfield

Yufeng Wu

Abstract

We extend a structural result by A. Dress and M. Steel, "Convex tree realizations of partitions," Applied Math Letters, 5 (1993), pp. 3-6., to show that the three-state Perfect Phylogeny problem reduces in polynomial time to the classic 2-SAT problem. We also give a more expanded exposition of the proof of the structural result from Dress and Steel. We hope this note will encourage additional researchers to try to solve the central open question: finding simple efficient solutions to the k-state Perfect Phylogeny problem for k > 3.

Full Text (PDF format)