{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:58Z","timestamp":1787323018125,"version":"build-2736575974"},"reference-count":32,"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":[[2015,1]]},"abstract":"<jats:p>Phylogenetic networks are used to display the relationship among different species whose evolution is not treelike, which is the case, for instance, in the presence of hybridization events or horizontal gene transfers. Tree inference methods such as maximum parsimony need to be modified in order to be applicable to networks. In this paper, we discuss two different definitions of maximum parsimony on networks, \u201chardwired\u201d and \u201csoftwired,\u201d and examine the complexity of computing them given a network topology and a character. By exploiting a link with the problem Multiterminal Cut, we show that computing the hardwired parsimony score for 2-state characters is polynomial-time solvable, while for characters with more states this problem becomes NP-hard but is still approximable and fixed parameter tractable in the parsimony score. On the other hand we show that, for the softwired definition, obtaining even weak approximation guarantees is already difficult for binary characters and restricted network topologies, and fixed-parameter tractable algorithms in the parsimony score are unlikely. On the positive side we show that computing the softwired parsimony score is fixed-parameter tractable in the level of the network, a natural parameter describing how tangled reticulate activity is in the network. Finally, we show that both the hardwired and the softwired parsimony scores can be computed efficiently using integer linear programming. The software has been made freely available.<\/jats:p>","DOI":"10.1137\/140959948","type":"journal-article","created":{"date-parts":[[2015,3,24]],"date-time":"2015-03-24T16:20:56Z","timestamp":1427214056000},"page":"559-585","source":"Crossref","is-referenced-by-count":26,"title":["On Computing the Maximum Parsimony Score of a Phylogenetic Network"],"prefix":"10.1137","volume":"29","author":[{"given":"Mareike","family":"Fischer","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leo","family":"van Iersel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Steven","family":"Kelk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Celine","family":"Scornavacca","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,3,24]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.13"},{"key":"atypb2","doi-asserted-by":"crossref","unstructured":"M.L. Arnold,\n                      Natural Hybridization and Evolution\n                      , Oxford University Press, New York, 1996.","DOI":"10.1093\/oso\/9780195099744.003.0006"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1080\/10635150500431197"},{"key":"atypb4","first-page":"109","author":"Bogart J.P.","year":"2003","journal-title":"NH"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792225297"},{"issue":"6","key":"atypb6","first-page":"64","author":"Edwards W.F.","year":"1964","journal-title":"Systematics Association Publication"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.2307\/2412923"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.2307\/2412116"},{"key":"atypb9","unstructured":"J. Flum and M. Grohe,\n                      Parameterized Complexity Theory\n                      , Springer, Berlin, 2006."},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-8858(82)80004-3"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"D.H. Huson, R. Rupp, and C. Scornavacca,\n                      Phylogenetic Networks: Concepts, Algorithms and Applications\n                      , Cambridge University Press, Cambridge, UK, 2011.","DOI":"10.1017\/CBO9780511974076"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1093\/sysbio\/sys062"},{"key":"atypb13","unstructured":"L.J.J. van Iersel, M. Fischer, S.M. Kelk, and C. Scornavacca,\n                      MPNet: Maximum Parsimony on Networks\n                      , http:\/\/homepages.cwi.nl\/ iersel\/MPNet\/ (2013)."},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jtbi.2010.10.032"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.07.027"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1093\/molbev\/msl163"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2008.119"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.04.019"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-7-9"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"D.R. Karger, P. Klein, C. Stein, M. Thorup, and N.E. Young,\n                      Rounding algorithms for a geometric embedding of minimum multiway cut\n                      , in Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing (STOC '99), 1999, pp. 668-678.","DOI":"10.1145\/301250.301430"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9708-5"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.128"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.micro.55.1.709"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"D.R. Maddison and K.S. Schulz, eds.\n                      The Tree of Life Web Project,\n                      http:\/\/www.tolweb.org (2007).","DOI":"10.11646\/zootaxa.1668.1.4"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1126\/science.1192243"},{"key":"atypb26","unstructured":"D.A. Morrison,\n                      Introduction to Phylogenetic Networks\n                      , RJR Productions, Uppsala, Sweden, 2011."},{"key":"atypb27","first-page":"125","author":"Nakhleh L.","year":"2009","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1109\/tcbb.2007.1018"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"R. Niedermeier,\n                      Invitation to Fixed Parameter Algorithms\n                      , Oxford Lecture Ser. Math. Appl. 31, Oxford University Press, Oxford, UK, 2006.","DOI":"10.1093\/acprof:oso\/9780198566076.003.0004"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF01681346"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"C. Semple and M. Steel,\n                      Phylogenetics\n                      , Oxford University Press, Oxford, UK, 2003.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9215-5"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140959948","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:37:19Z","timestamp":1787319439000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140959948"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140959948"],"URL":"https:\/\/doi.org\/10.1137\/140959948","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}