Parameterized and Approximation Algorithms for the MAF Problem in Multifurcating Trees
Conference Paper
Overview
Identity
Additional Document Info
Other
View All
Overview
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.
name of conference
Graph-Theoretic Concepts in Computer Science - 39th International Workshop, WG 2013, Lbeck, Germany, June 19-21, 2013, Revised Papers