research-article

The Complexity of Phylogeny Constraint Satisfaction Problems

Authors:

Manuel Bodirsky,

Trung Van PhamAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 18, Issue 3

Article No.: 23, Pages 1 - 42

https://doi.org/10.1145/3105907

Published: 02 August 2017 Publication History

Abstract

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 constraint satisfaction problems, 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’s Ramsey theorem for rooted trees, and universal algebra.

References

[1]

Samson Adepoju Adeleke and Peter M. Neumann. 1998. Relations Related to Betweenness: Their Structure and Automorphisms. Memoirs of the AMS, Vol. 623. American Mathematical Society.

[2]

Alfred V. Aho, Yehoshua Sagiv, Thomas G. Szymanski, and Jeffrey D. Ullman. 1981. Inferring a tree from lowest common ancestors with an application to the optimization of relational expressions. SIAM J. Comput. 10, 3 (1981), 405--421.

[3]

Libor Barto and Michael Pinsker. 2016. The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems. In Proceedings of the Conference on Logic in Computer Science (LICS’16), Martin Grohe, Eric Koskinen, and Natarajan Shankar (Eds.). ACM, 615--622.

Digital Library

[4]

Manuel Bodirsky. 2007. Cores of countably categorical structures. Log. Meth. Comput. Sci. 3, 1 (2007), 1--16.

[5]

Manuel Bodirsky. 2008. Constraint satisfaction problems with infinite templates. In Complexity of Constraints (A Collection of Survey Articles), Heribert Vollmer (Ed.). Lecture Notes in Computer Science, Vol. 5250. Springer, 196--228.

Digital Library

[6]

Manuel Bodirsky. 2012. Complexity Classification in Infinite-Domain Constraint Satisfaction. Mémoire d’rsquo;habilitation à diriger des recherches, Universit’eacute; Diderot, Paris 7. Available at arXiv:1201.0856. (2012).

[7]

Manuel Bodirsky. 2015. Ramsey classes: Examples and constructions. (2015). Proceedings of the 25th British Combinatorial Conference; arXiv:1502.05146.

[8]

Manuel Bodirsky, Hubie Chen, and Michael Pinsker. 2010. The reducts of equality up to primitive positive interdefinability. J. Symb. Log. 75, 4 (2010), 1249--1292.

[9]

Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. 2016a. The complexity of phylogeny constraint satisfaction. In Proceedings of the 33rd Symposium on Theoretical Aspects of Computer Science (STACS’rsquo;16) (LIPIcs), Nicolas Ollinger and Heribert Vollmer (Eds.), Vol. 47. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 20:1--20:13.

[10]

Manuel Bodirsky, Peter Jonsson, and Trung Van Pham. 2016b. The reducts of the homogeneous binary branching C-relation. J. Symb. Log. 81, 4 (2016), 1255--1297.

[11]

Manuel Bodirsky, Peter Jonsson, and Timo von Oertzen. 2011. Horn versus full first-order: Complexity dichotomies for algebraic constraint satisfaction. J. Log. Comput. 22, 3 (2011), 643--660.

Digital Library

[12]

Manuel Bodirsky and Jan Kára. 2008. The complexity of equality constraint languages. Theory Comput. Syst. 3, 2 (2008), 136--158. A conference version appeared in Proceedings of the Computer Science Russia (CSR’rsquo;06).

[13]

Manuel Bodirsky and Jan Kára. 2009. The complexity of temporal constraint satisfaction problems. J. Assoc. Comput. Mach. 57, 2 (2009), 1--41. An extended abstract appeared in Proceedings of the Symposium on Theory of Computing (STOC’rsquo;08).

Digital Library

[14]

Manuel Bodirsky and Jens K. Mueller. 2011. Rooted phylogeny problems. Log. Meth. Comput. Sci. 8, 4 (2011). An extended abstract appeared in the proceedings of ICDT’rsquo;10.

[15]

Manuel Bodirsky and Jaroslav Nešetřil. 2006. Constraint satisfaction with countable homogeneous templates. J. Log. Comput. 16, 3 (2006), 359--373.

Digital Library

[16]

Manuel Bodirsky and Michael Pinsker. 2011. Reducts of Ramsey structures. AMS Contemporary Mathematics, vol. 558 (Model Theoretic Methods in Finite Combinatorics) (2011), 489--519.

[17]

Manuel Bodirsky and Michael Pinsker. 2014. Minimal functions on the random graph. Israel J. Math. 200, 1 (2014), 251--296.

[18]

Manuel Bodirsky and Michael Pinsker. 2015a. Schaefer’rsquo;s theorem for graphs. J. Assoc. Comput. Mach. 62, 3 (2015), Article No. 19, 52 pages. A conference version appeared in Proceedings of STOC 2011, 655--664.

[19]

Manuel Bodirsky and Michael Pinsker. 2015b. Topological birkhoff. Trans. Amer. Math. Soc. 367 (2015), 2527--2549.

[20]

Manuel Bodirsky, Michael Pinsker, and András Pongrácz. 2014. Projective clone homomorphisms (2014). Preprint available at ArXiv:1409.4601.

[21]

Manuel Bodirsky, Michael Pinsker, and Todor Tsankov. 2013. Decidability of definability. J. Symbol. Log. 78, 4 (2013), 1036--1054. A conference version appeared in Proceedings of the Conference on Logic in Computer Science (LICS’rsquo;11).

[22]

V. G. Bodnarčuk, Lev A. Kalužnin, Victor Kotov, and Boris A. Romov. 1969. Galois theory for post algebras, part I and II. Cybernetics 5 (1969), 243--539.

[23]

David Bryant. 1997. Building trees, hunting for trees, and comparing trees. PhD-thesis at the University of Canterbury. (1997).

[24]

David Bryant and Mike Steel. 1995. Extension operations on sets of leaf-labelled trees. Adv. in Appl. Math. 16, 4 (1995), 425--453.

Digital Library

[25]

Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons. 2005. Classifying the complexity of constraints using finite algebras. SIAM J. Comput. 34 (2005), 720--742.

Digital Library

[26]

Peter J. Cameron. 1990. Oligomorphic Permutation Groups. Cambridge University Press, Cambridge.

[27]

Hubie Chen. 2006. A rendezvous of logic, complexity, and algebra. SIGACT News 37, 4 (2006), 85--114.

Digital Library

[28]

David Cohen, Peter Jeavons, Peter Jonsson, and Manolis Koubarakis. 2000. Building tractable disjunctive constraints. J. Assoc. Comput. Mach. 47, 5 (2000), 826--853.

Digital Library

[29]

Michael Garey and David Johnson. 1978. A Guide to NP-Completeness. CSLI Press, Stanford.

[30]

David Geiger. 1968. Closed systems of functions and predicates. Pac. J. Math. 27 (1968), 95--100.

[31]

Deirdre Haskell and Dugald Macpherson. 1994. Cell decompositions of C-minimal structures. Ann. Pure Appl. Logic 66 (1994), 113--162.

[32]

Monika Henzinger, Valerie King, and Tandy Warnow. 1996. Constructing a tree from homeomorphic subtrees, with applications to computational evolutionary biology. In Proceedings of the 7th Symposium on Discrete Algorithms (SODA’rsquo;96). 333--340.

[33]

Wilfrid Hodges. 1993. Model Theory. Cambridge University Press, Cambridge.

[34]

Jesper Jansson, Nguyen Bao Nguyen, and Wing-Kin Sung. 2006. Algorithms for combining rooted triplets into a galled phylogenetic network. SIAM J. Comput. 35, 5 (2006), 1098--1121.

Digital Library

[35]

Peter Jeavons. 1998. On the algebraic structure of combinatorial problems. Theor. Comput. Sci. 200 (1998), 185--204.

Digital Library

[36]

Klaus Leeb. 1973. Vorlesungen über Pascaltheorie. Arbeitsberichte des Instituts für Mathematische Maschinen und Datenverarbeitung, Vol. 6. Friedrich-Alexander-Universität Erlangen-Nürnberg.

[37]

Dugald Macpherson and Charles Steinhorn. 1996. On variants of o-minimality. Ann. Pure Appl. Logic 79, 2 (1996), 165--209.

[38]

Meei Pyng Ng, Mike Steel, and Nicholas C. Wormald. 2000. The difficulty of constructing a leaf-labelled tree including or avoiding given subtrees. Discrete Appl. Math. 98 (2000), 227--235.

Digital Library

[39]

Reinhard Pöschel and Lev A. Kalužnin. 1979. Funktionen-und Relationenalgebren. Deutscher Verlag der Wissenschaften, Berlin.

[40]

Michael Steel. 1992. The complexity of reconstructing trees from qualitative charaters and subtrees. J. Classif. 9 (1992), 91--116.

[41]

Mike A. Steel. 2016. Phylogeny - Discrete and Random Processes in Evolution.CBMS-NSF regional conference series in applied mathematics, Vol. 89. SIAM. 293 pages.

[42]

Ágnes Szendrei. 1986. Clones in Universal Algebra. Les Presses de l’rsquo;Universit’eacute; de Montr’eacute;al.

[43]

Tandy Warnow. 2017. Computational Phylogenetics: An Introduction to Designing Methods for Phylogeny Estimation. To be published by Cambridge University Press in 2017.

Cited By

Bodirsky MBodor B(2024)A Complexity Dichotomy in Spatial Reasoning via Ramsey TheoryACM Transactions on Computation Theory10.1145/364944516:2(1-39)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3649445
Bodirsky MJonsson PMartin BMottet ASemanišinová Ž(2024)Complexity Classification Transfer for CSPs via Algebraic ProductsSIAM Journal on Computing10.1137/22M153430453:5(1293-1353)Online publication date: 12-Sep-2024
https://doi.org/10.1137/22M1534304
Chatziafratis VMakarychev K(2023)Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00024(253-284)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00024
Show More Cited By

Index Terms

The Complexity of Phylogeny Constraint Satisfaction Problems
1. Theory of computation
  1. Computational complexity and cryptography
    1. Complexity theory and logic
    2. Problems, reductions and completeness

Recommendations

The complexity of rooted phylogeny problems
ICDT '10: Proceedings of the 13th International Conference on Database Theory

Several computational problems in phylogenetic reconstruction can be formulated as restrictions of the following general problem: given a formula in conjunctive normal form where the atomic formulas are rooted triples, is there a rooted binary tree that ...
Constraint satisfaction tractability from semi-lattice operations on infinite sets

A famous result by Jeavons, Cohen, and Gyssens shows that every Constraint Satisfaction Problem (CSP) where the constraints are preserved by a semi-lattice operation can be solved in polynomial time. This is one of the basic facts for the so-called ...
The Optimization Complexity of Constraint Satisfaction Problems

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 18, Issue 3

July 2017

273 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/3130378

Editor:
Orna Kupferman
School of Computer Science and Engineering, Hebrew University, Israel

Issue’s Table of Contents

Copyright © 2017 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 August 2017

Accepted: 01 May 2017

Revised: 01 May 2017

Received: 01 August 2016

Published in TOCL Volume 18, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

European Research Council
Austrian Science Fund (FWF)
European Research Council under the European Community’s Seventh Framework Programme
Vietnam National Foundation for Science and Technology Development (NAFOSTED)
German Science Foundation
Swedish Research Council (VR)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
125
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)1

Reflects downloads up to 23 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Bodirsky MBodor B(2024)A Complexity Dichotomy in Spatial Reasoning via Ramsey TheoryACM Transactions on Computation Theory10.1145/364944516:2(1-39)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3649445
Bodirsky MJonsson PMartin BMottet ASemanišinová Ž(2024)Complexity Classification Transfer for CSPs via Algebraic ProductsSIAM Journal on Computing10.1137/22M153430453:5(1293-1353)Online publication date: 12-Sep-2024
https://doi.org/10.1137/22M1534304
Chatziafratis VMakarychev K(2023)Triplet Reconstruction and all other Phylogenetic CSPs are Approximation Resistant2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00024(253-284)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00024
Dabrowski KJonsson POrdyniak SOsipov G(2023)Solving infinite-domain CSPs using the patchwork propertyArtificial Intelligence10.1016/j.artint.2023.103880317(103880)Online publication date: Apr-2023
https://doi.org/10.1016/j.artint.2023.103880
Mottet APinsker M(2022)Smooth approximations and CSPs over finitely bounded homogeneous structuresProceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3531130.3533353(1-13)Online publication date: 2-Aug-2022
https://dl.acm.org/doi/10.1145/3531130.3533353
Pinsker M(2022)Current Challenges in Infinite-Domain Constraint Satisfaction: Dilemmas of the Infinite Sheep2022 IEEE 52nd International Symposium on Multiple-Valued Logic (ISMVL)10.1109/ISMVL52857.2022.00019(80-87)Online publication date: May-2022
https://doi.org/10.1109/ISMVL52857.2022.00019
Baader FRydval J(2022)Using Model Theory to Find Decidable and Tractable Description Logics with Concrete DomainsJournal of Automated Reasoning10.1007/s10817-022-09626-266:3(357-407)Online publication date: 4-May-2022
https://dl.acm.org/doi/10.1007/s10817-022-09626-2
Behrisch MVargas-García E(2021)On a stronger reconstruction notion for monoids and clonesForum Mathematicum10.1515/forum-2020-0205Online publication date: 25-Sep-2021
https://doi.org/10.1515/forum-2020-0205
Jonsson PLagerkvist VRoy B(2021)Fine-Grained Time Complexity of Constraint Satisfaction ProblemsACM Transactions on Computation Theory10.1145/343438713:1(1-32)Online publication date: 21-Jan-2021
https://dl.acm.org/doi/10.1145/3434387
Bodirsky MBodor B(2021)Canonical Polymorphisms of Ramsey Structures and the Unique Interpolation Property2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)10.1109/LICS52264.2021.9470683(1-13)Online publication date: 29-Jun-2021
https://doi.org/10.1109/LICS52264.2021.9470683
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents