Cookies

We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.


Durham Research Online
You are in:

Constraint satisfaction problems for reducts of homogeneous graphs.

Bodirsky, Manuel and Martin, Barnaby and Pinsker, Michael and Pongrácz, András (2016) 'Constraint satisfaction problems for reducts of homogeneous graphs.', in 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Dagstuhl, Germany: Schloss Dagstuhl, Leibniz-Zentrum für Informatik, p. 119. LIPIcs : Leibniz international proceedings in informatics. (55).

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.

Item Type:Book chapter
Full text:(VoR) Version of Record
Available under License - Creative Commons Attribution.
Download PDF
(444Kb)
Full text:(AM) Accepted Manuscript
Available under License - Creative Commons Attribution.
Download PDF
(507Kb)
Status:Peer-reviewed
Publisher Web site:https://doi.org/10.4230/LIPIcs.ICALP.2016.119
Publisher statement:© Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz; licensed under Creative Commons License CC-BY
Date accepted:15 April 2016
Date deposited:17 October 2016
Date of first online publication:August 2016
Date first made open access:No date available

Save or Share this output

Export:
Export
Look up in GoogleScholar