{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T01:53:25Z","timestamp":1787363605655,"version":"build-2736575974"},"reference-count":31,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Given two rooted phylogenetic trees on the same set of taxa $X$, the Maximum Agreement Forest (maf) problem asks to find a forest that is, in a certain sense, common to both trees and has a minimum number of components. The Maximum Acyclic Agreement Forest (maaf) problem has the additional restriction that the components of the forest cannot have conflicting ancestral relations in the input trees. There has been considerable interest in the special cases of these problems in which the input trees are required to be binary. However, in practice, phylogenetic trees are rarely binary, due to uncertainty about the precise order of speciation events. Here, we show that the general, nonbinary version of maf has a polynomial-time 4-approximation and a fixed-parameter tractable (exact) algorithm that runs in $O(4^k {\\rm poly}(n))$ time, where $n=|X|$ and $k$ is the number of components of the agreement forest minus one. Moreover, we show that a $c$-approximation algorithm for nonbinary maf and a $d$-approximation algorithm for the classical problem Directed Feedback Vertex Set (dfvs) can be combined to yield a $d(c+3)$-approximation for nonbinary maaf. The algorithms for maf have been implemented and made publicly available.<\/jats:p>","DOI":"10.1137\/120903567","type":"journal-article","created":{"date-parts":[[2014,1,14]],"date-time":"2014-01-14T11:20:59Z","timestamp":1389698459000},"page":"49-66","source":"Crossref","is-referenced-by-count":11,"title":["Approximation Algorithms for Nonbinary Agreement Forests"],"prefix":"10.1137","volume":"28","author":[{"given":"Leo","family":"van Iersel","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nela","family":"Leki\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leen","family":"Stougie","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,1,14]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-005-0315-9"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-004-0228-0"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.1419"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1177\/117693430700300017"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.10.002"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-004-0229-z"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1109\/tcbb.2007.1019"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.08.008"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.11.004"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq548"},{"key":"atypb11","unstructured":"J. Collins,<i>Rekernelisation Algorithms in Hybrid Phylogenies<\/i> MSc. thesis, University of Canterbury, Christchurch, New Zealand, 2009."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0166"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"atypb14","unstructured":"J. Flum and M. Grohe,<i>Parameterized Complexity Theory<\/i> Springer, New York, 2006."},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"O. Gascuel, ed.<i>Mathematics of Evolution and Phylogeny<\/i> Oxford University Press, Oxford, UK, 2005.","DOI":"10.1093\/oso\/9780198566106.001.0001"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"O. Gascuel and M. Steel, eds.<i>Reconstructing Evolution: New Mathematical and Computational Advances<\/i> Oxford University Press, Oxford, UK, 2007.","DOI":"10.1093\/oso\/9780199208227.001.0001"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00062-5"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"D. H. Huson, R. Rupp, and C. Scornavacca,<i>Phylogenetic Networks: Concepts, Algorithms and Applications<\/i> Cambridge University Press, Cambridge, UK, 2010.","DOI":"10.1017\/CBO9780511974076"},{"key":"atypb19","first-page":"430","author":"van Iersel L. J. J.","year":"2012","journal-title":"New York"},{"key":"atypb20","unstructured":"L. J. J. van Iersel, S. M. Kelk, N. Leki\u0107, and L. Stougie,<i>MAF: Maximum Agreement Forests for Nonbinary Trees<\/i> 2012. Software available online at http:\/\/homepages.cwi.nl\/ $\\sim$iersel\/MAF\/."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1137\/120864350"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.86"},{"key":"atypb23","unstructured":"D. A. Morrison,<i>An Introduction to Phylogenetic Networks<\/i> RJR Productions, 2011. Available online at http:\/\/www.rjr-productions.org\/Networks\/."},{"key":"atypb24","first-page":"125","author":"Nakhleh L.","year":"2009","journal-title":"New York"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,<i>Invitation to Fixed-Parameter Algorithms<\/i> Oxford Lecture Ser. Math. Appl. 31, Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.003.0004"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2012.134"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.011"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2012.0192"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"C. Semple and M. Steel,<i>Phylogenetics<\/i> Oxford University Press, Oxford, UK, 2003.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"atypb30","unstructured":"C. Whidden, R. G. Beiko, and N. Zeh,<i>Fixed-Parameter and Approximation Algorithms for Maximum Agreement Forests<\/i> preprint, arXiv:1108.2664v1 [q-bio.PE], 2011."},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/110845045"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120903567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:14:31Z","timestamp":1787321671000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120903567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":31,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/120903567"],"URL":"https:\/\/doi.org\/10.1137\/120903567","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}