{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,30]],"date-time":"2025-07-30T15:35:59Z","timestamp":1753889759137,"version":"3.41.2"},"reference-count":37,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","license":[{"start":{"date-parts":[[2011,11,24]],"date-time":"2011-11-24T00:00:00Z","timestamp":1322092800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/arxiv.org\/licenses\/nonexclusive-distrib\/1.0"}],"funder":[{"DOI":"10.13039\/501100000780","name":"European Commission","doi-asserted-by":"crossref","award":["257039"],"award-info":[{"award-number":["257039"]}],"id":[{"id":"10.13039\/501100000780","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Several computational problems in phylogenetic reconstruction can be\nformulated as restrictions of the following general problem: given a formula in\nconjunctive normal form where the literals are rooted triples, is there a\nrooted binary tree that satisfies the formula? If the formulas do not contain\ndisjunctions, the problem becomes the famous rooted triple consistency problem,\nwhich can be solved in polynomial time by an algorithm of Aho, Sagiv,\nSzymanski, and Ullman. If the clauses in the formulas are restricted to\ndisjunctions of negated triples, Ng, Steel, and Wormald showed that the problem\nremains NP-complete. We systematically study the computational complexity of\nthe problem for all such restrictions of the clauses in the input formula. For\ncertain restricted disjunctions of triples we present an algorithm that has\nsub-quadratic running time and is asymptotically as fast as the fastest known\nalgorithm for the rooted triple consistency problem. We also show that any\nrestriction of the general rooted phylogeny problem that does not fall into our\ntractable class is NP-complete, using known results about the complexity of\nBoolean constraint satisfaction problems. Finally, we present a pebble game\nargument that shows that the rooted triple consistency problem (and also all\ngeneralizations studied in this paper) cannot be solved by Datalog.<\/jats:p>","DOI":"10.2168\/lmcs-7(4:6)2011","type":"journal-article","created":{"date-parts":[[2012,6,20]],"date-time":"2012-06-20T09:05:51Z","timestamp":1340183151000},"source":"Crossref","is-referenced-by-count":4,"title":["The Complexity of Rooted Phylogeny Problems"],"prefix":"10.46298","volume":"Volume 7, Issue 4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8228-3611","authenticated-orcid":false,"given":"Manuel","family":"Bodirsky","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens K","family":"Mueller","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"25203","published-online":{"date-parts":[[2011,11,24]]},"reference":[{"key":"10.2168\/LMCS-7(4:6)2011_AHV","unstructured":"S. Abiteboul, R. Hull, and V. Vianu.Foundations of Databases. Addison Wesley, 1995."},{"issue":"11","key":"10.2168\/LMCS-7(4:6)2011_Allen","doi-asserted-by":"crossref","first-page":"832","DOI":"10.1145\/182.358434","volume":"26","author":"J. F. Allen","year":"1983","journal-title":"Communications of the ACM"},{"key":"10.2168\/LMCS-7(4:6)2011_AdelekeNeumann","doi-asserted-by":"crossref","unstructured":"Samson Adepoju Adeleke and Peter M. Neumann.Relations related to betweenness: their structure and automorphisms, volume 623 ofMemoirs of the AMS 131. American Mathematical Society, 1998.","DOI":"10.1090\/memo\/0623"},{"issue":"3","key":"10.2168\/LMCS-7(4:6)2011_ASSU","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1137\/0210030","volume":"10","author":"A.V. Aho, Y. Sagiv, T.G. Szymanski, and","year":"1981","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-7(4:6)2011_AfratiCosmadakisYannakakis","doi-asserted-by":"publisher","DOI":"10.1145\/113413.113415"},{"key":"10.2168\/LMCS-7(4:6)2011_BodDalJournal","unstructured":"Manuel Bodirsky and V\u00edctor Dalmau. Datalog and constraint satisfaction with infinite templates.An extended abstract appeared in the proceedings of STACS'06. The full version is available online at arXiv:0809.2386 [cs.LO], 2008."},{"key":"10.2168\/LMCS-7(4:6)2011_BiggsCubic","doi-asserted-by":"crossref","unstructured":"Norman Biggs. Constructions for cubic graphs with large girth.Electronic Journal of Combinatorics, 5, 1998.","DOI":"10.37236\/1386"},{"issue":"2","key":"10.2168\/LMCS-7(4:6)2011_BroxvallJonsson","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1016\/S0004-3702(03)00075-4","volume":"149","author":"Mathias Broxvall and Peter Jonsson","year":"2003","journal-title":"Artificial Intelligence"},{"key":"10.2168\/LMCS-7(4:6)2011_CSPSurvey","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/1-4020-3817-8_8","volume":"207","author":"A. Bulatov, P. Jeavons, and A. Krokhin","year":"2005","journal-title":"In: Structural Theory of Automata, Semigroups and Universal Algebra (Montreal, 2003), NATO Science Series II: Mathematics, Physics, Chemistry"},{"key":"10.2168\/LMCS-7(4:6)2011_BodirskyKutzAI","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.artint.2006.12.004","volume":"171","author":"Manuel Bodirsky and Martin Kutz","year":"2007","journal-title":"Artificial Intelligence"},{"key":"10.2168\/LMCS-7(4:6)2011_ll","doi-asserted-by":"publisher","DOI":"10.1145\/1740582.1740583"},{"issue":"3","key":"10.2168\/LMCS-7(4:6)2011_BodirskyNesetrilJLC","doi-asserted-by":"crossref","first-page":"359","DOI":"10.1093\/logcom\/exi083","volume":"16","author":"Manuel Bodirsky and Jaroslav Nesetril","year":"2006","journal-title":"Journal of Logic and Computation"},{"key":"10.2168\/LMCS-7(4:6)2011_BodirskySurvey","doi-asserted-by":"crossref","unstructured":"Manuel Bodirsky. Constraint satisfaction problems with infinite templates. In Heribert Vollmer, editor,Complexity of Constraints (a collection of survey articles), pages 196-228. Springer, LNCS 5250, 2008.","DOI":"10.1007\/978-3-540-92800-3_8"},{"key":"10.2168\/LMCS-7(4:6)2011_Bryant","unstructured":"David Bryant. Building trees, hunting for trees, and comparing trees. PhD-thesis at the University of Canterbury, 1997."},{"key":"10.2168\/LMCS-7(4:6)2011_BryantSteel","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1006\/aama.1995.1020","volume":"16","author":"D. Bryant and M. Steel","year":"1995","journal-title":"Advances in Applied Mathematics"},{"key":"10.2168\/LMCS-7(4:6)2011_Oligo","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511549809"},{"issue":"6","key":"10.2168\/LMCS-7(4:6)2011_CreignouHerbrard","first-page":"499","volume":"31","author":"Nadia Creignou and Jean-Jacques H\u00e9brard","year":"1997","journal-title":"Informatique Theorique et Applications 1997"},{"key":"10.2168\/LMCS-7(4:6)2011_Creignou","doi-asserted-by":"crossref","unstructured":"Nadia Creignou, Sanjeev Khanna, and Madhu Sudan.Complexity Classifications of Boolean Constraint Satisfaction Problems. SIAM Monographs on Discrete Mathematics and Applications 7, 2001.","DOI":"10.1137\/1.9780898718546"},{"key":"10.2168\/LMCS-7(4:6)2011_Cornell","doi-asserted-by":"crossref","unstructured":"Thomas Cornell. On determining the consistency of partial descriptions of trees. InProceedings of the ACL, pages 163-170, 1994.","DOI":"10.3115\/981732.981755"},{"issue":"1","key":"10.2168\/LMCS-7(4:6)2011_Dechter","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1016\/0004-3702(92)90043-W","volume":"55","author":"Rina Dechter","year":"1992","journal-title":"Artificial Intelligence"},{"key":"10.2168\/LMCS-7(4:6)2011_Dekker","unstructured":"M. C. H. Dekker. Reconstruction methods for derivation trees. Masters thesis, Vrije Universiteit, Amsterdam, 1986."},{"key":"10.2168\/LMCS-7(4:6)2011_Duentsch","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/s10462-004-5899-8","volume":"23","author":"Ivo Duentsch","year":"2005","journal-title":"Artificial Intelligence Review"},{"key":"10.2168\/LMCS-7(4:6)2011_EbbinghausFlum","unstructured":"H.-D. Ebbinghaus and J. Flum.Finite Model Theory. Springer, Berlin, Heidelberg, New York, 1999. 2nd edition."},{"key":"10.2168\/LMCS-7(4:6)2011_FederVardi","first-page":"57","volume":"28","author":"Tom\u00e1s Feder and Moshe Vardi","year":"1999","journal-title":"SIAM Journal on Computing"},{"key":"10.2168\/LMCS-7(4:6)2011_GroheThesis","unstructured":"Martin Grohe. The structure of fixed-point logics. PhD-thesis at the Albert-Ludwigs Universit\u00e4t, Freiburg i. Br., 1994."},{"issue":"3","key":"10.2168\/LMCS-7(4:6)2011_HirschAlgebraicLogic","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1093\/logcom\/7.3.309","volume":"7","author":"R. Hirsch","year":"1997","journal-title":"Journal of Logic and Computation"},{"key":"10.2168\/LMCS-7(4:6)2011_HenzingerKingWarnow","unstructured":"Monika Henzinger, Valerie King, and Tandy Warnow. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. InProceedings of the 7th Symposium on Discrete Algorithms (SODA'96), pages 333-340, 1996."},{"key":"10.2168\/LMCS-7(4:6)2011_HodgesLong","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511551574"},{"key":"10.2168\/LMCS-7(4:6)2011_Immerman","doi-asserted-by":"crossref","unstructured":"N. Immerman.Descriptive Complexity. Graduate Texts in Computer Science, Springer, 1998.","DOI":"10.1007\/978-1-4612-0539-5"},{"issue":"1","key":"10.2168\/LMCS-7(4:6)2011_KolaitisVardiDatalog","doi-asserted-by":"crossref","first-page":"110","DOI":"10.1006\/jcss.1995.1055","volume":"51","author":"Phokion G. Kolaitis and Moshe Y. Vardi","year":"1995","journal-title":"Journal of Computer and System Sciences"},{"key":"10.2168\/LMCS-7(4:6)2011_KolaitisVardi","doi-asserted-by":"crossref","unstructured":"Phokion G. Kolaitis and Moshe Y. Vardi. Conjunctive-query containment and constraint satisfaction. InProceedings of PODS, pages 205-213, 1998.","DOI":"10.1145\/275487.275511"},{"key":"10.2168\/LMCS-7(4:6)2011_PathConsistency","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/0004-3702(77)90007-8","volume":"8","author":"A. K. Mackworth","year":"1977","journal-title":"Artificial Intelligence"},{"key":"10.2168\/LMCS-7(4:6)2011_Montanari","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/0020-0255(74)90008-5","volume":"7","author":"Ugo Montanari","year":"1974","journal-title":"Information Sciences"},{"key":"10.2168\/LMCS-7(4:6)2011_NgSteelWormald","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1016\/S0166-218X(99)00160-2","volume":"98","author":"Meei Pyng Ng, Mike Steel, and Nicholas C","year":"2000","journal-title":"Discrete Applied Mathematics"},{"key":"10.2168\/LMCS-7(4:6)2011_Post","doi-asserted-by":"crossref","unstructured":"Emil L. Post. The two-valued iterative systems of mathematical logic.Annals of Mathematics studies, 5, 1941.","DOI":"10.1515\/9781400882366"},{"key":"10.2168\/LMCS-7(4:6)2011_Steel","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/BF02618470","volume":"9","author":"Michael Steel","year":"1992","journal-title":"Journal of Classification"},{"key":"10.2168\/LMCS-7(4:6)2011_ThorupI","unstructured":"Mikkel Thorup, Jacob Holm, and Kristian de Lichtenberg. Poly-logarithmic deterministic fully-dynamic graph algorithms I: connectivity and minimum spanning tree. Technical report, Department of Computer Science, University of Copenhagen, 1998."}],"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/906\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/906\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,11]],"date-time":"2023-04-11T19:58:55Z","timestamp":1681243135000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/906"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,11,24]]},"references-count":37,"URL":"https:\/\/doi.org\/10.2168\/lmcs-7(4:6)2011","relation":{"is-same-as":[{"id-type":"arxiv","id":"1110.0693","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1110.0693","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2011,11,24]]},"article-number":"906"}}