Cargando…

A duality based 2-approximation algorithm for maximum agreement forest

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

Descripción completa

Detalles Bibliográficos
Autores principales: Olver, Neil, Schalekamp, Frans, van der Ster, Suzanne, Stougie, Leen, van Zuylen, Anke
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer Berlin Heidelberg 2022
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9945189/
https://www.ncbi.nlm.nih.gov/pubmed/36845754
http://dx.doi.org/10.1007/s10107-022-01790-y
_version_ 1784892083949010944
author Olver, Neil
Schalekamp, Frans
van der Ster, Suzanne
Stougie, Leen
van Zuylen, Anke
author_facet Olver, Neil
Schalekamp, Frans
van der Ster, Suzanne
Stougie, Leen
van Zuylen, Anke
author_sort Olver, Neil
collection PubMed
description 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.
format Online
Article
Text
id pubmed-9945189
institution National Center for Biotechnology Information
language English
publishDate 2022
publisher Springer Berlin Heidelberg
record_format MEDLINE/PubMed
spelling pubmed-99451892023-02-23 A duality based 2-approximation algorithm for maximum agreement forest Olver, Neil Schalekamp, Frans van der Ster, Suzanne Stougie, Leen van Zuylen, Anke Math Program Full Length Paper 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. Springer Berlin Heidelberg 2022-03-21 2023 /pmc/articles/PMC9945189/ /pubmed/36845754 http://dx.doi.org/10.1007/s10107-022-01790-y Text en © The Author(s) 2022 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Full Length Paper
Olver, Neil
Schalekamp, Frans
van der Ster, Suzanne
Stougie, Leen
van Zuylen, Anke
A duality based 2-approximation algorithm for maximum agreement forest
title A duality based 2-approximation algorithm for maximum agreement forest
title_full A duality based 2-approximation algorithm for maximum agreement forest
title_fullStr A duality based 2-approximation algorithm for maximum agreement forest
title_full_unstemmed A duality based 2-approximation algorithm for maximum agreement forest
title_short A duality based 2-approximation algorithm for maximum agreement forest
title_sort duality based 2-approximation algorithm for maximum agreement forest
topic Full Length Paper
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC9945189/
https://www.ncbi.nlm.nih.gov/pubmed/36845754
http://dx.doi.org/10.1007/s10107-022-01790-y
work_keys_str_mv AT olverneil adualitybased2approximationalgorithmformaximumagreementforest
AT schalekampfrans adualitybased2approximationalgorithmformaximumagreementforest
AT vanderstersuzanne adualitybased2approximationalgorithmformaximumagreementforest
AT stougieleen adualitybased2approximationalgorithmformaximumagreementforest
AT vanzuylenanke adualitybased2approximationalgorithmformaximumagreementforest
AT olverneil dualitybased2approximationalgorithmformaximumagreementforest
AT schalekampfrans dualitybased2approximationalgorithmformaximumagreementforest
AT vanderstersuzanne dualitybased2approximationalgorithmformaximumagreementforest
AT stougieleen dualitybased2approximationalgorithmformaximumagreementforest
AT vanzuylenanke dualitybased2approximationalgorithmformaximumagreementforest