Skip to main content

Research Repository

Advanced Search

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

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

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs Thumbnail


Authors

Manuel Bodirsky

Michael Pinsker

András Pongrácz



Contributors

Ioannis Chatzigiannakis
Editor

Michael Mitzenmacher
Editor

Yuval Rabani
Editor

Davide Sangiorgi
Editor

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.

Citation

Bodirsky, M., Martin, B., Pinsker, M., & Pongrácz, A. (2016). Constraint Satisfaction Problems for Reducts of Homogeneous Graphs. In I. Chatzigiannakis, M. Mitzenmacher, Y. Rabani, & D. Sangiorgi (Eds.), 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016. https://doi.org/10.4230/lipics.icalp.2016.119

Conference Name 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy
Conference Location Rome, Italy
Start Date Jul 12, 2016
End Date Jul 15, 2016
Acceptance Date Apr 15, 2016
Publication Date Aug 1, 2016
Deposit Date Oct 14, 2016
Publicly Available Date Mar 29, 2024
Series Title LIPIcs : Leibniz international proceedings in informatics
Series Number 55
Series ISSN 1868-8969
Book Title 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016.
DOI https://doi.org/10.4230/lipics.icalp.2016.119
Public URL https://durham-repository.worktribe.com/output/1150163
Related Public URLs https://arxiv.org/abs/1602.05819

Files






You might also like



Downloadable Citations