License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2016.119
URN: urn:nbn:de:0030-drops-62543
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6254/
Go to the corresponding LIPIcs Volume Portal

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

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

pdf-format:
LIPIcs-ICALP-2016-119.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{bodirsky_et_al:LIPIcs:2016:6254,
  author =	{Manuel Bodirsky and Barnaby Martin and Michael Pinsker and Andr{\'a}s Pongr{\'a}cz},
  title =	{{Constraint Satisfaction Problems for Reducts of Homogeneous Graphs}},
  booktitle =	{43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
  pages =	{119:1--119:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-013-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{55},
  editor =	{Ioannis Chatzigiannakis and Michael Mitzenmacher and Yuval Rabani and Davide Sangiorgi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6254},
  URN =		{urn:nbn:de:0030-drops-62543},
  doi =		{10.4230/LIPIcs.ICALP.2016.119},
  annote =	{Keywords: Constraint Satisfaction, Homogeneous Graphs, Computational Complexity, Universal Algebra, Ramsey Theory}
}

Keywords: Constraint Satisfaction, Homogeneous Graphs, Computational Complexity, Universal Algebra, Ramsey Theory
Collection: 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Issue Date: 2016
Date of publication: 23.08.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI