A duality based 2-approximation algorithm for maximum agreement forest

Neil Olver; Frans Schalekamp; Suzanne van der Ster; Leen Stougie; Anke van Zuylen

doi:10.1007/s10107-022-01790-y

A duality based 2-approximation algorithm for maximum agreement forest

Neil Olver^*, Frans Schalekamp, Suzanne van der Ster, Leen Stougie, Anke van Zuylen

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

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.

Original language	English
Pages (from-to)	811-853
Number of pages	43
Journal	Mathematical Programming
Volume	198
Issue number	1
DOIs	https://doi.org/10.1007/s10107-022-01790-y
Publication status	Published - Mar 2023

Bibliographical note

Funding Information:
We acknowledge the support of the Tinbergen Institute and the Hausdorff Research Institute for Mathematics, where portions of this research were pursued. We thank the anonymous referees for their very careful readings and detailed feedback on improving the presentation. N.O. was supported in part by NWO Veni grant 639.071.307 and NWO Vidi grant 016.Vidi.189.087. F.S. was supported in part by NSF grants CCF-1526067 and CCF-1522054. L.S. was supported by NWO Gravitation Programme Networks 024.002.003. A.v.Z. was supported in part by grant #359525 from the Simons Foundation.

Funding Information:
N.O. was supported in part by NWO Veni grant 639.071.307 and NWO Vidi grant 016.Vidi.189.087. F.S. was supported in part by NSF grants CCF-1526067 and CCF-1522054. L.S. was supported by NWO Gravitation Programme Networks 024.002.003. A.v.Z. was supported in part by grant #359525 from the Simons Foundation.

Publisher Copyright:
© 2022, The Author(s).

Keywords

Computational biology
Maximum agreement forest
Phylogenetic tree
SPR distance
Subtree prune-and-regraft distance

UN SDGs

This output contributes to the following UN Sustainable Development Goals (SDGs)

Access to Document

10.1007/s10107-022-01790-y

Persistent URL (handle)

Persistent link

Cite this

@article{35fca8bc94a24a72b1c12bad069c371d,

title = "A duality based 2-approximation algorithm for maximum agreement forest",

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 = "Computational biology, Maximum agreement forest, Phylogenetic tree, SPR distance, Subtree prune-and-regraft distance",

author = "Neil Olver and Frans Schalekamp and {van der Ster}, Suzanne and Leen Stougie and {van Zuylen}, Anke",

note = "Funding Information: We acknowledge the support of the Tinbergen Institute and the Hausdorff Research Institute for Mathematics, where portions of this research were pursued. We thank the anonymous referees for their very careful readings and detailed feedback on improving the presentation. N.O. was supported in part by NWO Veni grant 639.071.307 and NWO Vidi grant 016.Vidi.189.087. F.S. was supported in part by NSF grants CCF-1526067 and CCF-1522054. L.S. was supported by NWO Gravitation Programme Networks 024.002.003. A.v.Z. was supported in part by grant #359525 from the Simons Foundation. Funding Information: N.O. was supported in part by NWO Veni grant 639.071.307 and NWO Vidi grant 016.Vidi.189.087. F.S. was supported in part by NSF grants CCF-1526067 and CCF-1522054. L.S. was supported by NWO Gravitation Programme Networks 024.002.003. A.v.Z. was supported in part by grant #359525 from the Simons Foundation. Publisher Copyright: {\textcopyright} 2022, The Author(s).",

year = "2023",

month = mar,

doi = "10.1007/s10107-022-01790-y",

language = "English",

volume = "198",

pages = "811--853",

journal = "Mathematical Programming",

issn = "0025-5610",

publisher = "Springer-Verlag GmbH and Co. KG",

number = "1",

}

TY - JOUR

T1 - A duality based 2-approximation algorithm for maximum agreement forest

AU - Olver, Neil

AU - Schalekamp, Frans

AU - van der Ster, Suzanne

AU - Stougie, Leen

AU - van Zuylen, Anke

N1 - Funding Information: We acknowledge the support of the Tinbergen Institute and the Hausdorff Research Institute for Mathematics, where portions of this research were pursued. We thank the anonymous referees for their very careful readings and detailed feedback on improving the presentation. N.O. was supported in part by NWO Veni grant 639.071.307 and NWO Vidi grant 016.Vidi.189.087. F.S. was supported in part by NSF grants CCF-1526067 and CCF-1522054. L.S. was supported by NWO Gravitation Programme Networks 024.002.003. A.v.Z. was supported in part by grant #359525 from the Simons Foundation. Funding Information: N.O. was supported in part by NWO Veni grant 639.071.307 and NWO Vidi grant 016.Vidi.189.087. F.S. was supported in part by NSF grants CCF-1526067 and CCF-1522054. L.S. was supported by NWO Gravitation Programme Networks 024.002.003. A.v.Z. was supported in part by grant #359525 from the Simons Foundation. Publisher Copyright: © 2022, The Author(s).

PY - 2023/3

Y1 - 2023/3

N2 - 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.

AB - 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.

KW - Computational biology

KW - Maximum agreement forest

KW - Phylogenetic tree

KW - SPR distance

KW - Subtree prune-and-regraft distance

UR - http://www.scopus.com/inward/record.url?scp=85126769997&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85126769997&partnerID=8YFLogxK

U2 - 10.1007/s10107-022-01790-y

DO - 10.1007/s10107-022-01790-y

M3 - Article

AN - SCOPUS:85126769997

SN - 0025-5610

VL - 198

SP - 811

EP - 853

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -