Constraint satisfaction problems for reducts of homogeneous graphs

DOI10.4230/LIPICS.ICALP.2016.119MaRDI QIDQ4598261zbMATH OpenOpenAlexFDO

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

Publication date 19 December 2017

Full work available at URL https://arxiv.org/abs/1602.05819

zbMATH Keywords

computational complexityconstraint satisfactionRamsey theoryuniversal algebrahomogeneous graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Structural characterization of families of graphs (05C75) Model theory of denumerable and separable structures (03C15) Applications of universal algebra in computer science (08A70)

Abstract: For $ngeq3$, let $(H_n,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 $H_n$ whose relations are first-order definable in $(H_n,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.

Recommendations

• Constraint satisfaction problems for reducts of homogeneous graphs
• Constraint Satisfaction with Countable Homogeneous Templates
• Computer Science Logic
• The complexity of the list homomorphism problem for graphs
• The complexity of the list homomorphism problem for graphs

Cited in

(7)

• Constraint Satisfaction with Countable Homogeneous Templates
• Constraint satisfaction problems for reducts of homogeneous graphs
• Computer Science Logic
• Projection merging
• Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
• scientific article; zbMATH DE number 7199580 (Why is no real title available?)
• Smooth approximations and CSPs over finitely bounded homogeneous structures

This page was built for publication: Constraint satisfaction problems for reducts of homogeneous graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4598261)