{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,18]],"date-time":"2026-01-18T05:01:32Z","timestamp":1768712492651,"version":"3.49.0"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T00:00:00Z","timestamp":1647820800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T00:00:00Z","timestamp":1647820800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1526067"],"award-info":[{"award-number":["CCF-1526067"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1522054"],"award-info":[{"award-number":["CCF-1522054"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["Veni 639.071.307"],"award-info":[{"award-number":["Veni 639.071.307"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["359525"],"award-info":[{"award-number":["359525"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["016.Vidi.189.087"],"award-info":[{"award-number":["016.Vidi.189.087"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["024.002.003"],"award-info":[{"award-number":["024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2023,3]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s10107-022-01790-y","type":"journal-article","created":{"date-parts":[[2022,3,21]],"date-time":"2022-03-21T11:03:04Z","timestamp":1647860584000},"page":"811-853","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["A duality based 2-approximation algorithm for maximum\u00a0agreement forest"],"prefix":"10.1007","volume":"198","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8897-5459","authenticated-orcid":false,"given":"Neil","family":"Olver","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Frans","family":"Schalekamp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Suzanne","family":"van der Ster","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anke","family":"van Zuylen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,21]]},"reference":[{"issue":"1","key":"1790_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00026-001-8006-8","volume":"5","author":"BL Allen","year":"2001","unstructured":"Allen, B.L., Steel, M.: Subtree transfer operations and their induced metrics on evolutionary trees. Ann. Comb. 5(1), 1\u201315 (2001)","journal-title":"Ann. Comb."},{"key":"1790_CR2","doi-asserted-by":"crossref","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics (LATIN), pp. 88\u201394 (2000)","DOI":"10.1007\/10719839_9"},{"issue":"8","key":"1790_CR3","doi-asserted-by":"publisher","first-page":"1419","DOI":"10.1089\/cmb.2006.13.1419","volume":"13","author":"ML Bonet","year":"2006","unstructured":"Bonet, M.L., John, K.S., Mahindru, R., Amenta, N.: Approximating subtree distances between phylogenies. J. Comput. Biol. 13(8), 1419\u20131434 (2006)","journal-title":"J. Comput. Biol."},{"issue":"3","key":"1790_CR4","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1016\/j.jda.2007.10.002","volume":"6","author":"M Bordewich","year":"2008","unstructured":"Bordewich, M., McCartin, C., Semple, C.: A 3-approximation algorithm for the subtree distance between phylogenies. J. Discret. Algorithms 6(3), 458\u2013471 (2008)","journal-title":"J. Discret. Algorithms"},{"issue":"4","key":"1790_CR5","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/s00026-004-0229-z","volume":"8","author":"M Bordewich","year":"2004","unstructured":"Bordewich, M., Semple, C.: On the computational complexity of the rooted subtree prune and regraft distance. Ann. Comb. 8(4), 409\u2013423 (2004)","journal-title":"Ann. Comb."},{"issue":"5","key":"1790_CR6","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/j.ipl.2004.11.004","volume":"93","author":"F Chataigner","year":"2005","unstructured":"Chataigner, F.: Approximating the maximum agreement forest on $$k$$ trees. Inf. Process. Lett. 93(5), 239\u2013244 (2005)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"1790_CR7","doi-asserted-by":"publisher","first-page":"867","DOI":"10.1007\/s00453-015-0087-6","volume":"76","author":"J Chen","year":"2016","unstructured":"Chen, J., Shi, F., Wang, J.: Approximating maximum agreement forest on multiple binary trees. Algorithmica 76(4), 867\u2013889 (2016)","journal-title":"Algorithmica"},{"key":"1790_CR8","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/978-3-319-59575-7_12","volume-title":"Bioinformatics Research and Applications","author":"Z-Z Chen","year":"2017","unstructured":"Chen, Z.-Z., Harada, Y., Wang, L.: A new 2-approximation algorithm for rSPR distance. In: Cai, Z., Daescu, O., Li, M. (eds.) Bioinformatics Research and Applications, pp. 128\u2013139. Springer International Publishing, Cham (2017)"},{"key":"1790_CR9","doi-asserted-by":"crossref","unstructured":"Chen, Z.-Z., Machida, E., Wang, L.: A cubic-time 2-approximation algorithm for rSPR distance. arXiv preprint arXiv:1609.04029 (2016)","DOI":"10.1007\/978-3-319-42634-1_38"},{"key":"1790_CR10","doi-asserted-by":"crossref","unstructured":"Chen, Z.Z., Machida, E., Wang, L.: An improved approximation algorithm for rSPR distance. In International Computing and Combinatorics Conference, pp. 468\u2013479. Springer (2016)","DOI":"10.1007\/978-3-319-42634-1_38"},{"key":"1790_CR11","unstructured":"Darwin, C.: Notebook B: Transmutation of species (1837?-1838). In: John van Wyhe: The Complete Work of Charles Darwin Online (2002). http:\/\/darwin-online.org.uk\/"},{"key":"1790_CR12","volume-title":"Mathematics of Evolution and Phylogeny","year":"2005","unstructured":"Gascuel, O. (ed.): Mathematics of Evolution and Phylogeny. Oxford University Press Inc., Oxford (2005)"},{"key":"1790_CR13","first-page":"144","volume-title":"Approximation Algorithms for NP-hard Problems","author":"MX Goemans","year":"1997","unstructured":"Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-hard Problems, pp. 144\u2013191. PWS Publishing Co., Boston (1997)"},{"key":"1790_CR14","doi-asserted-by":"crossref","unstructured":"Harel, D.: A linear time algorithm for the lowest common ancestors problem. In Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS), pp. 308\u2013319 (1980)","DOI":"10.1109\/SFCS.1980.6"},{"issue":"2","key":"1790_CR15","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM J. Comput. 13(2), 338\u2013355 (1984)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"1790_CR16","first-page":"153","volume":"71","author":"J Hein","year":"1996","unstructured":"Hein, J., Jiang, T., Wang, L., Zhang, K.: On the complexity of comparing evolutionary trees. Discret Appl. Math. J. Comb. Algorithms Inf. Comput. Sci. 71(1\u20133), 153\u2013169 (1996)","journal-title":"Discret Appl. Math. J. Comb. Algorithms Inf. Comput. Sci."},{"key":"1790_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511974076","volume-title":"Phylogenetic Networks: Concepts","author":"D Huson","year":"2010","unstructured":"Huson, D., Rupp, R., Scornavacca, C.: Phylogenetic Networks: Concepts. Cambridge University Press, Algorithms and Applications, Cambridge (2010)"},{"key":"1790_CR18","volume-title":"The Problem Solving Handbook for Computational Biology and Bioinformatics","author":"L Nakhleh","year":"2009","unstructured":"Nakhleh, L.: Evolutionary phylogenetic networks: models and issues. In: Heath, L., Ramakrishnan, N. (eds.) The Problem Solving Handbook for Computational Biology and Bioinformatics. Springer, New York (2009)"},{"key":"1790_CR19","unstructured":"Olver, N., Schalekamp, F., Stougie, L., van Zuylen, A.: Implementation of the MAF algorithm and compact formulation. Available at http:\/\/nolver.net\/maf and http:\/\/fransschalekamp.com\/MAF (2018)"},{"key":"1790_CR20","unstructured":"Rodrigues, E.M.: Algoritmos para Compara\u00e7\u00e3o de \u00c1rvores Filogen\u00e9ticas e o Problema dos Pontos de Recombina\u00e7\u00e3o. PhD thesis, University of S\u00e3o Paulo, Brazil (2003). Chapter 7, available at http:\/\/www.ime.usp.br\/~estela\/studies\/tese-traducao-cp7.ps.gz"},{"key":"1790_CR21","doi-asserted-by":"crossref","unstructured":"Rodrigues, E.M., Sagot, M.-F., Wakabayashi, Y.: Some approximation results for the maximum agreement forest problem. In: Proceedings of APPROX-RANDOM, Lecture Notes in Computer Science, pp. 159\u2013169. Springer (2001)","DOI":"10.1007\/3-540-44666-4_19"},{"issue":"1\u20133","key":"1790_CR22","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.tcs.2006.12.011","volume":"374","author":"EM Rodrigues","year":"2007","unstructured":"Rodrigues, E.M., Sagot, M.-F., Wakabayashi, Y.: The maximum agreement forest problem: approximation algorithms and computational experiments. Theor. Comput. Sci. 374(1\u20133), 91\u2013110 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"1790_CR23","unstructured":"Schalekamp, F., van Zuylen, A., van\u00a0der Ster, S.: A duality based 2-approximation algorithm for maximum agreement forest. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), Vol.\u00a055 of LIPIcs, pp. 70:1\u201370:14. Leibniz-Zentrum f\u00fcr Informatik, (2016)"},{"key":"1790_CR24","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198509424.001.0001","volume-title":"Phylogenetics","author":"C Semple","year":"2003","unstructured":"Semple, C., Steel, M.: Phylogenetics. Oxford University Press, Oxford (2003)"},{"issue":"1","key":"1790_CR25","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/s10878-015-9921-7","volume":"32","author":"F Shi","year":"2015","unstructured":"Shi, F., Feng, Q., You, J., Wang, J.: Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees. J. Comb. Optim. 32(1), 111\u2013143 (2015)","journal-title":"J. Comb. Optim."},{"issue":"2","key":"1790_CR26","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90181-8","volume":"48","author":"M Steel","year":"1993","unstructured":"Steel, M., Warnow, T.: Kaikoura tree theorems: Computing the maximum agreement subtree. Inf. Process. Lett. 48(2), 77\u201382 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"1790_CR27","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1137\/120903567","volume":"28","author":"L van Iersel","year":"2014","unstructured":"van Iersel, L., Kelk, S., Lekic, N., Stougie, L.: Approximation algorithms for nonbinary agreement forests. SIAM J. Discret. Math. 28(1), 49\u201366 (2014)","journal-title":"SIAM J. Discret. Math."},{"issue":"4","key":"1790_CR28","doi-asserted-by":"publisher","first-page":"1431","DOI":"10.1137\/110845045","volume":"42","author":"C Whidden","year":"2013","unstructured":"Whidden, C., Beiko, R.G., Zeh, N.: Fixed-parameter algorithms for maximum agreement forests. SIAM J. Comput. 42(4), 1431\u20131466 (2013)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1790_CR29","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1109\/TCBB.2018.2802911","volume":"16","author":"C Whidden","year":"2019","unstructured":"Whidden, C., Matsen, F.A.: Calculating the unrooted subtree prune-and-regraft distance. IEEE\/ACM Trans. Comput. Biol. Bioinform. 16(3), 898\u2013911 (2019)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"key":"1790_CR30","doi-asserted-by":"crossref","unstructured":"Whidden, C., Zeh, N.: A unifying view on approximation and FPT of agreement forests. In: Algorithms in Bioinformatics. Lecture Notes in Computer Science, Vol. 5724 , pp. 390\u2013402. Springer, Berlin Heidelberg (2009)","DOI":"10.1007\/978-3-642-04241-6_32"},{"issue":"2","key":"1790_CR31","doi-asserted-by":"publisher","first-page":"190","DOI":"10.1093\/bioinformatics\/btn606","volume":"25","author":"Y Wu","year":"2009","unstructured":"Wu, Y.: A practical method for exact computation of subtree prune and regraft distance. Bioinformatics 25(2), 190\u2013196 (2009)","journal-title":"Bioinformatics"},{"key":"1790_CR32","doi-asserted-by":"crossref","unstructured":"Wu, Y., Wang, J.: Fast computation of the exact hybridization number of two phylogenetic trees. In: Bioinformatics Research and Applications. Lecture Notes in Computer Science, Vol. 6053, pp. 203\u2013214. Springer, Berlin Heidelberg (2010)","DOI":"10.1007\/978-3-642-13078-6_23"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01790-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-022-01790-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-022-01790-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,19]],"date-time":"2023-11-19T02:49:18Z","timestamp":1700362158000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-022-01790-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,21]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,3]]}},"alternative-id":["1790"],"URL":"https:\/\/doi.org\/10.1007\/s10107-022-01790-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,3,21]]},"assertion":[{"value":"1 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 March 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}