A duality based 2-approximation algorithm for maximum agreement forest
Authors:
Open Access
- 21 March 2022
- journal article
- research article
- Published by Springer Nature in Mathematical Programming
- Vol. 198 (1) , 811-853
Abstract
We give a 2-approximation algorithm for the Maximum Agreement Forest problem on two rooted binary trees. This NP-hard problem has been studied extensively in the past two decades, since it can be used to compute the rooted Subtree Prune-and-Regraft (rSPR) distance between two phylogenetic trees. Our algorithm is combinatorial and its running time is quadratic in the input size. To prove the approximation guarantee, we construct a feasible dual solution for a novel exponential-size linear programming formulation. In addition, we show this linear program has a smaller integrality gap than previously known formulations, and we give an equivalent compact formulation, showing that it can be solved in polynomial time.Keywords
All Related Versions
Funding Information
- National Science Foundation (CCF-1526067, CCF-1522054)
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (Veni 639.071.307)
- Simons Foundation (359525)
- Nederlandse Organisatie voor Wetenschappelijk Onderzoek (016.Vidi.189.087, 024.002.003)
This publication has 23 references indexed in Scilit:
- Fixed-Parameter Algorithms for Maximum Agreement ForestsSIAM Journal on Computing, 2013
- A practical method for exact computation of subtree prune and regraft distanceBioinformatics, 2008
- A 3-approximation algorithm for the subtree distance between phylogeniesJournal of Discrete Algorithms, 2008
- The maximum agreement forest problem: Approximation algorithms and computational experimentsTheoretical Computer Science, 2007
- Approximating Subtree Distances Between PhylogeniesJournal of Computational Biology, 2006
- Approximating the Maximum Agreement Forest on k treesInformation Processing Letters, 2005
- On the Computational Complexity of the Rooted Subtree Prune and Regraft DistanceAnnals of Combinatorics, 2005
- Subtree Transfer Operations and Their Induced Metrics on Evolutionary TreesAnnals of Combinatorics, 2001
- Kaikoura tree theorems: Computing the maximum agreement subtreeInformation Processing Letters, 1993
- Fast Algorithms for Finding Nearest Common AncestorsSIAM Journal on Computing, 1984