2018/11/14 by Neil Olver, Frans Schalekamp, Olver, Neil +7
Biochemistry, Genetics and Molecular Biology · Computer Science · #68W25 #90C27 #92D15 #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Natural Language Processing Techniques
paper · pdf · doi:10.48550/arxiv.1811.05916
openalex publication_date 2018/11/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 linear programming formulation. In addition, we show this linear program is stronger than previously known formulations, and we give a compact formulation, showing that it can be solved in polynomial time