Constraint satisfaction problems for reducts of homogeneous graphs

2016/02/18 by Bodirsky, Manuel, Martin, Barnaby, Pinsker, Michael +1 · 3 citations
#Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO)

paper · doi:10.48550/arxiv.1602.05819

Abstract

For n≥ 3, 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 Γ with domain H_n whose relations are first-order definable in (H_n,E) the constraint satisfaction problem for Γ 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.

Cited by

• A CSP approach to Graph Sandwich Problems
• Janus-faces of temporal constraint languages: a dichotomy of expressivity
• The Network Satisfaction Problem for Relation Algebras with at most 4 Atoms

Related

• An order out of nowhere: a new algorithm for infinite-domain CSPs
• Complexity of Homogeneous Co-Boolean Constraint Satisfaction Problems
• Structures preserved by primitive actions of S_ω
• Relational Width of First-Order Expansions of Homogeneous Graphs with Bounded Strict Width
• Equations in oligomorphic clones and the Constraint Satisfaction Problem for ω-categorical structures