Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees Academic Article

abstract

• 2014 Elsevier B.V. We study parameterized algorithms and approximation algorithms for the maximum agreement forest problem, which, for two given leaf-labeled trees, is to find a maximum forest that is a subgraph of both trees. The problem was motivated by research in phylogenetics. For parameterized algorithms, while the problem is known to be fixed-parameter tractable for binary trees, it was an open problem whether the problem is still fixed-parameter tractable for general trees. We resolve this open problem by developing an O(3kn)-time parameterized algorithm for general trees. Our techniques on tree structures also lead to a polynomial-time approximation algorithm of ratio 3 for the problem, giving the first constant-ratio approximation algorithm for general trees.

authors

• Chen, Jianer
• Sze, Sing-Hoi

published proceedings

• THEORETICAL COMPUTER SCIENCE

altmetric score

• 3

author list (cited authors)

• Chen, J., Fan, J., & Sze, S.

citation count

• 15

complete list of authors

• Chen, Jianer||Fan, Jia-Hao||Sze, Sing-Hoi

publication date

• January 2015

publisher

• Elsevier  Publisher

published in

• Theoretical Computer Science  Journal

keywords

• Approximation Algorithm
• Fixed-parameter Tractability
• Maximum Agreement Forest
• Phylogenetic Tree

Digital Object Identifier (DOI)

• 10.1016/j.tcs.2014.10.031

start page

• 496

end page

• 512

volume

• 562

issue

• C

URL

• http%3A%2F%2Fdx.doi.org%2F10.1016%2Fj.tcs.2014.10.031