{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:10:06Z","timestamp":1787389806620,"version":"build-2736575974"},"reference-count":40,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2012,1]]},"abstract":"<jats:p>We show that the problem of computing the hybridization number of two rooted binary phylogenetic trees on the same set of taxa $X$ has a constant factor polynomial-time approximation if and only if the problem of computing a minimum-size feedback vertex set in a directed graph (DFVS) has a constant factor polynomial-time approximation. The latter problem, which asks for a minimum number of vertices to be removed from a directed graph to transform it into a directed acyclic graph, is one of the problems in Karp's seminal 1972 list of 21 NP-complete problems. Despite considerable attention from the combinatorial optimization community, it remains to this day unknown whether a constant factor polynomial-time approximation exists for DFVS. Our result thus places the (in)approximability of hybridization number in a much broader complexity context, and as a consequence we obtain that it inherits inapproximability results from the problem Vertex Cover. On the positive side, we use results from the DFVS literature to give an $\\text{O}( \\log r \\log \\log r)$ approximation for the hybridization number where $r$ is the correct value.<\/jats:p>","DOI":"10.1137\/120864350","type":"journal-article","created":{"date-parts":[[2012,11,20]],"date-time":"2012-11-20T14:50:11Z","timestamp":1353423011000},"page":"1635-1656","source":"Crossref","is-referenced-by-count":20,"title":["Cycle Killer...Qu'est-ce que c'est? On the Comparative Approximability of Hybridization Number and Directed Feedback Vertex Set"],"prefix":"10.1137","volume":"26","author":[{"given":"Steven","family":"Kelk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leo","family":"van Iersel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nela","family":"Leki\u0107","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Simone","family":"Linz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Celine","family":"Scornavacca","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":[[2012,11,20]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480196305124"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s00285-005-0315-9"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-004-0228-0"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.132"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1177\/117693430700300017"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2007.10.002"},{"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.1145\/1411509.1411511"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq548"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0166"},{"key":"atypb12","first-page":"33","author":"Dinur I.","year":"2002","journal-title":"New York"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,<i>Parameterized Complexity<\/i> Springer-Verlag, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009191"},{"key":"atypb16","unstructured":"J. Flum and M. Grohe,<i>Parameterized Complexity Theory<\/i> Springer-Verlag, Berlin, 2006."},{"key":"atypb17","doi-asserted-by":"crossref","unstructured":"O. Gascuel, ed.<i>Mathematics of Evolution and Phylogeny<\/i> Oxford University Press, Oxford, 2005.","DOI":"10.1093\/oso\/9780198566106.001.0001"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"O. Gascuel and M. Steel, eds.<i>Reconstructing Evolution: New Mathematical and Computational Advances<\/i> Oxford University Press, New York, 2007.","DOI":"10.1093\/oso\/9780199208227.001.0001"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm049"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(96)00062-5"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.aml.2008.08.018"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp217"},{"key":"atypb23","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":"atypb24","doi-asserted-by":"publisher","DOI":"10.1093\/gbe\/evq077"},{"key":"atypb25","unstructured":"V. Kann,<i>On the Approximability of NP-Complete Optimization Problems<\/i> Ph.D. thesis, \\nobreak Department of Numerical Analysis and Computing Science, Royal Institute of Technology, Stockholm, 1992."},{"key":"atypb26","first-page":"85","author":"Karp R. M.","year":"1972","journal-title":"New York"},{"key":"atypb27","unstructured":"S. M. Kelk and C. Scornavacca,<i>Constructing minimal phylogenetic networks from softwired clusters is fixed parameter tractable<\/i> preprint, 2011; http:\/\/arxiv.org\/abs\/1108.3653."},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.128"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"atypb30","doi-asserted-by":"crossref","unstructured":"L. Nakhleh,<i>Evolutionary phylogenetic networks: Models and issues<\/i> in The Problem Solving Handbook for Computational Biology and Bioinformatics, Springer-Verlag, New York, 2009.","DOI":"10.1007\/978-0-387-09760-2_7"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,<i>Invitation to Fixed Parameter Algorithms (Oxford Lecture Series in Mathematics and Its Applications)<\/i> Oxford University Press, New York, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.003.0001"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.011"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"C. Semple,<i>Hybridization networks<\/i> in Reconstructing Evolution: New Mathematical and Computational Advances, Oxford University Press, New York, 2007.","DOI":"10.1093\/oso\/9780199208227.003.0010"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"C. Semple and M. Steel,<i>Phylogenetics<\/i> Oxford University Press, Oxford, 2003.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200760"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2010.10.032"},{"key":"atypb39","first-page":"141","author":"Whidden C.","year":"2010","journal-title":"Berlin"},{"key":"atypb40","unstructured":"C. Whidden, R. G. Beiko, and N. Zeh,<i>Fixed-parameter and approximation algorithms for maximum agreement forests<\/i> preprint, 2011, http:\/\/arxiv.org\/abs\/1108.2664."},{"key":"atypb41","first-page":"390","author":"Whidden C.","year":"2009","journal-title":"Berlin"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/120864350","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:25Z","timestamp":1787321965000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/120864350"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,1]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,1]]}},"alternative-id":["10.1137\/120864350"],"URL":"https:\/\/doi.org\/10.1137\/120864350","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,1]]}}}