Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00327
The agreement problem for unrooted phylogenetic trees is FPT
Celine Scornavacca, Leo van Iersel, Steven Kelk, and David Bryant
Vol. 18, no. 3, pp. 385-392, 2014. Regular paper.
Abstract A collection T of k unrooted phylogenetic trees on different leaf sets is said to be strictly compatible or in agreement if there exists a tree T such that each tree in T can be obtained from T by deleting leaves and suppressing degree-2 vertices. The problem of determining if a set of unrooted trees is in agreement has been proved NP-hard in 1992. Here, we show that an f(k) ·n algorithm exists, for some computable function f of k, proving that strict compatibility of unrooted phylogenetic trees is fixed-parameter tractable with respect to the number k of trees. Designing a practical FPT algorithm remains an open problem.
Submitted: March 2014.
Reviewed: June 2014.
Revised: June 2014.
Accepted: June 2014.
Final: June 2014.
Published: June 2014.
Communicated by Dorothea Wagner
article (PDF)
BibTeX