A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees
Lists
Only you see this
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},
}