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...
Autores principales: | , , , , |
---|---|
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 |