{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,20]],"date-time":"2026-07-20T06:19:07Z","timestamp":1784528347940,"version":"3.55.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,31]],"date-time":"2017-07-31T00:00:00Z","timestamp":1501459200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Research Council","award":["257039 and No. 681988"],"award-info":[{"award-number":["257039 and No. 681988"]}]},{"name":"Austrian Science Fund","award":["P27600"],"award-info":[{"award-number":["P27600"]}]},{"name":"European Research Council under the European Community\u2019s Seventh Framework Programme","award":["257039"],"award-info":[{"award-number":["257039"]}]},{"DOI":"10.13039\/100007224","name":"Vietnam National Foundation for Science and Technology Development","doi-asserted-by":"crossref","award":["101.99-2016.16"],"award-info":[{"award-number":["101.99-2016.16"]}],"id":[{"id":"10.13039\/100007224","id-type":"DOI","asserted-by":"crossref"}]},{"name":"German Science Foundation","award":["622397"],"award-info":[{"award-number":["622397"]}]},{"DOI":"10.13039\/501100004359","name":"Swedish Research Council","doi-asserted-by":"crossref","award":["621-2012-3239"],"award-info":[{"award-number":["621-2012-3239"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Logic"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            We systematically study the computational complexity of a broad class of computational problems in phylogenetic reconstruction. The class contains, for example, the rooted triple consistency problem, forbidden subtree problems, the quartet consistency problem, and many other problems studied in the bioinformatics literature. The studied problems can be described as\n            <jats:italic>constraint satisfaction problems<\/jats:italic>\n            , where the constraints have a first-order definition over the rooted triple relation. We show that every such phylogeny problem can be solved in polynomial time or is NP-complete. On the algorithmic side, we generalize a well-known polynomial-time algorithm of Aho, Sagiv, Szymanski, and Ullman for the rooted triple consistency problem. Our algorithm repeatedly solves linear equation systems to construct a solution in polynomial time. We then show that every phylogeny problem that cannot be solved by our algorithm is NP-complete. Our classification establishes a dichotomy for a large class of infinite structures that we believe is of independent interest in universal algebra, model theory, and topology. The proof of our main result combines results and techniques from various research areas: a recent classification of the model-complete cores of the reducts of the homogeneous binary branching C-relation, Leeb\u2019s Ramsey theorem for rooted trees, and universal algebra.\n          <\/jats:p>","DOI":"10.1145\/3105907","type":"journal-article","created":{"date-parts":[[2017,8,2]],"date-time":"2017-08-02T19:36:12Z","timestamp":1501702572000},"page":"1-42","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["The Complexity of Phylogeny Constraint Satisfaction Problems"],"prefix":"10.1145","volume":"18","author":[{"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[{"name":"Institut f\u00fcr Algebra, TU Dresden, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Jonsson","sequence":"additional","affiliation":[{"name":"Department of Computer and Information Science, Link\u00f6pings Universitet, Sweden"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Trung Van","family":"Pham","sequence":"additional","affiliation":[{"name":"Department of Mathematics for Computer Science, Institute of Mathematics, Vietnam Academy of Science and Technology, Hanoi, Vietnam"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,8,2]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Neumann","author":"Adeleke Samson Adepoju","year":"1998"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0210030"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934544"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.2168\/LMCS-3(1:2)2007"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92800-3_8"},{"key":"e_1_2_1_6_1","volume-title":"Universit\u2019eacute","author":"Bodirsky Manuel"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 25th British Combinatorial Conference; arXiv:1502","author":"Bodirsky Manuel","year":"2015"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl\/1286198146"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS\u2019rsquo;16)","volume":"47","author":"Bodirsky Manuel","year":"2016"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/jsl.2016.37"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exr011"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-9083-9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667058"},{"key":"e_1_2_1_14_1","volume-title":"Mueller","author":"Bodirsky Manuel","year":"2011"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/exi083"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/558\/11058"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-014-1042-y"},{"key":"e_1_2_1_18_1","volume-title":"conference version appeared in Proceedings of STOC","author":"Bodirsky Manuel","year":"2015"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-2014-05975-8"},{"key":"e_1_2_1_20_1","volume-title":"Projective clone homomorphisms","author":"Bodirsky Manuel","year":"2014"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.2178\/jsl.7804020"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01070906"},{"key":"e_1_2_1_23_1","unstructured":"David Bryant. 1997. Building trees hunting for trees and comparing trees. PhD-thesis at the University of Canterbury. (1997).  David Bryant. 1997. Building trees hunting for trees and comparing trees. PhD-thesis at the University of Canterbury. (1997)."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1995.1020"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700376676"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511549809"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1189056.1189076"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/355483.355485"},{"key":"e_1_2_1_29_1","volume-title":"A Guide to NP-Completeness","author":"Garey Michael"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1968.27.95"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(94)90064-7"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the 7th Symposium on Discrete Algorithms (SODA\u2019rsquo;96)","author":"Henzinger Monika","year":"1996"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704446529"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(97)00230-2"},{"key":"e_1_2_1_36_1","volume-title":"Arbeitsberichte des Instituts f\u00fcr Mathematische Maschinen und Datenverarbeitung","volume":"6","author":"Leeb Klaus","year":"1973"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0168-0072(95)00037-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00160-2"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-5547-1"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974485"},{"key":"e_1_2_1_42_1","volume-title":"Clones in Universal Algebra. Les Presses de l\u2019rsquo;Universit\u2019eacute","author":"Szendrei \u00c1gnes"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316882313"}],"container-title":["ACM Transactions on Computational Logic"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105907","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3105907","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:30:04Z","timestamp":1750217404000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3105907"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,31]]},"references-count":43,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3105907"],"URL":"https:\/\/doi.org\/10.1145\/3105907","relation":{},"ISSN":["1529-3785","1557-945X"],"issn-type":[{"value":"1529-3785","type":"print"},{"value":"1557-945X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,31]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-08-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}