A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees

Feng Shi, Jianxin Wang, Yufei Yang, Qilong Feng, Weilong Li, Jianer ChenScience China Information Sciences 2016 · OpenReview

Abstract

The Maximum Agreement Forest (MAF) problem on two given phylogenetic trees is an important NP-hard problem in the field of computational biology. In this paper, we study the parameterized version of the MAF problem: given two unrooted (multifurcating) phylogenetic trees T 1 and T 2 with the same leaf-label set L, and a parameter k, either construct an agreement forest of at most k trees for T 1 and T 2, or report that no such a forest exists. Whether there is a fixed-parameter tractable algorithm for this problem was posed as an open problem several times in the literature. In this paper, we resolve this open problem by presenting a parameterized algorithm of running time O(4k n 5) for the problem.
BibTeX
@article{shi2016fixed,
  author = {Feng Shi and Jianxin Wang and Yufei Yang and Qilong Feng and Weilong Li and Jianer Chen},
  title = {{A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees}},
  journal = {Science China Information Sciences},
  year = {2016},
  url = {https://openreview.net/forum?id=qS8uATTog5},
}
Figure