The Three-state Perfect Phylogeny Problem Reduces to 2-SAT
Dan Gusfield, Yufeng Wu · Communications in Information and Systems · 2009
We extend a structural result by A. Dress and M. Steel [3], to show that the threestate 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 [3].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.