2026-07-22T04:44:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6254 2024-03-06T10:37:53Z ddc:004 open_access

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs Bodirsky, Manuel Martin, Barnaby Pinsker, Michael Pongrácz, András Constraint Satisfaction Homogeneous Graphs Computational Complexity Universal Algebra Ramsey Theory 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Manuel Bodirsky and Barnaby Martin and Michael Pinsker and András Pongrácz 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.119 urn:nbn:de:0030-drops-62543 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.119 eng https://creativecommons.org/licenses/by/3.0/legalcode