Document Open Access Logo

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Authors Manuel Bodirsky, Barnaby Martin, Michael Pinsker, András Pongrácz

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.119.pdf
  • Filesize: 443 kB
  • 14 pages

Document Identifiers

Author Details

Manuel Bodirsky
Barnaby Martin
Michael Pinsker
András Pongrácz

Cite AsGet BibTex

Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz. Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 119:1-119:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.119

Abstract

For n >= 3, let (Hn, E) denote the n-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on n vertices. We show that for all structures Gamma with domain Hn whose relations are first-order definable in (Hn, E) the constraint satisfaction problem for Gamma is either in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.
Keywords
  • Constraint Satisfaction
  • Homogeneous Graphs
  • Computational Complexity
  • Universal Algebra
  • Ramsey Theory

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Libor Barto, Marcin Kozik, and Todd Niven. The CSP dichotomy holds for digraphs with no sources and no sinks (a positive answer to a conjecture of Bang-Jensen and Hell). SIAM Journal on Computing, 38(5), 2009. Google Scholar
  2. Libor Barto, Jakub Opršal, and Michael Pinsker. The wonderland of reflections. Preprint arXiv:1510.04521, 2015. Google Scholar
  3. Manuel Bodirsky. Cores of countably categorical structures. Logical Methods in Computer Science, 3(1):1-16, 2007. Google Scholar
  4. Manuel Bodirsky. Complexity classification in infinite-domain constraint satisfaction. Mémoire d'habilitation à diriger des recherches, Université Diderot - Paris 7. Available at arXiv:1201.0856, 2012. Google Scholar
  5. Manuel Bodirsky, Hubie Chen, Jan Kára, and Timo von Oertzen. Maximal infinite-valued constraint languages. Theoretical Computer Science (TCS), 410:1684-1693, 2009. A preliminary version appeared at ICALP'07. Google Scholar
  6. Manuel Bodirsky and Jan Kára. The complexity of equality constraint languages. Theory of Computing Systems, 3(2):136-158, 2008. A conference version appeared in the proceedings of Computer Science Russia (CSR'06). Google Scholar
  7. Manuel Bodirsky and Jan Kára. The complexity of temporal constraint satisfaction problems. Journal of the ACM, 57(2):1-41, 2009. An extended abstract appeared in the Proceedings of the Symposium on Theory of Computing (STOC'08). Google Scholar
  8. Manuel Bodirsky, Barnaby Martin, and Antoine Mottet. Constraint satisfaction problems over the integers with successor. In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, pages 256-267, 2015. Google Scholar
  9. Manuel Bodirsky and Antoine Mottet. Reducts of finitely bounded homogeneous structures, and lifting tractability from finite-domain constraint satisfaction. Submitted. Preprint available under ArXiv:1601.04520, 2016. Google Scholar
  10. Manuel Bodirsky and Jaroslav Nešetřil. Constraint satisfaction with countable homogeneous templates. Journal of Logic and Computation, 16(3):359-373, 2006. Google Scholar
  11. Manuel Bodirsky and Michael Pinsker. Reducts of Ramsey structures. AMS Contemporary Mathematics, vol. 558 (Model Theoretic Methods in Finite Combinatorics), pages 489-519, 2011. Google Scholar
  12. Manuel Bodirsky and Michael Pinsker. Minimal functions on the random graph. Israel Journal of Mathematics, 200(1):251-296, 2014. Google Scholar
  13. Manuel Bodirsky and Michael Pinsker. Schaefer’s theorem for graphs. Journal of the ACM, 62(3):Article no. 19, 1-52, 2015. A conference version appeared in the Proceedings of STOC 2011, pages 655-664. Google Scholar
  14. Manuel Bodirsky and Michael Pinsker. Topological Birkhoff. Transactions of the American Mathematical Society, 367:2527-2549, 2015. Google Scholar
  15. Manuel Bodirsky, Michael Pinsker, and András Pongrácz. Projective clone homomorphisms. Preprint arXiv:1409.4601, 2014. Google Scholar
  16. Manuel Bodirsky and Michał Wrona. Equivalence constraint satisfaction problems. In Proceedings of Computer Science Logic, volume 16 of LIPICS, pages 122-136. Dagstuhl Publishing, September 2012. Google Scholar
  17. Andrei A. Bulatov. A dichotomy theorem for constraint satisfaction problems on a 3-element set. Journal of the ACM, 53(1):66-120, 2006. Google Scholar
  18. Andrei A. Bulatov, Andrei A. Krokhin, and Peter G. Jeavons. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34:720-742, 2005. Google Scholar
  19. Tomás Feder and Moshe Y. Vardi. The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory. SIAM Journal on Computing, 28:57-104, 1999. Google Scholar
  20. L. Haddad and Ivo G. Rosenberg. Finite clones containing all permutations. Canadian Journal of Mathematics, 46(5):951-970, 1994. Google Scholar
  21. Pavol Hell and Jaroslav Nešetřil. On the complexity of H-coloring. Journal of Combinatorial Theory, Series B, 48:92-110, 1990. Google Scholar
  22. Peter Jeavons, David Cohen, and Marc Gyssens. Closure properties of constraints. Journal of the ACM, 44(4):527-548, 1997. Google Scholar
  23. Alistair H. Lachlan and Robert E. Woodrow. Countable ultrahomogeneous undirected graphs. Transactions of the AMS, 262(1):51-94, 1980. Google Scholar
  24. Jaroslav Nešetřil and Vojtěch Rödl. The partite construction and Ramsey set systems. Discrete Mathematics, 75(1-3):327-334, 1989. Google Scholar
  25. Emil L. Post. The two-valued iterative systems of mathematical logic. Annals of Mathematics Studies, 5, 1941. Google Scholar
  26. Thomas J. Schaefer. The complexity of satisfiability problems. In Proceedings of the Symposium on Theory of Computing (STOC), pages 216-226, 1978. Google Scholar
  27. Katrin Tent and Martin Ziegler. A course in model theory. Lecture Notes in Logic. Cambridge University Press, 2012. Google Scholar
  28. Simon Thomas. Reducts of the random graph. Journal of Symbolic Logic, 56(1):176-181, 1991. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact