Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees Conference Paper uri icon

abstract

  • 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 the 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(3k n)-time parameterized algorithm for the problem on 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 the problem on general trees. © 2013 Springer-Verlag.

author list (cited authors)

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

citation count

  • 4

publication date

  • January 2013