Constraint satisfaction problems for reducts of homogeneous graphs

Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongracz, Andras

doi:10.1137/16m1082974

Constraint satisfaction problems for reducts of homogeneous graphs

Bodirsky, Manuel; Martin, Barnaby; Pinsker, Michael; Pongracz, Andras

Authors

Manuel Bodirsky

Dr Barnaby Martin barnaby.d.martin@durham.ac.uk
Associate Professor

Michael Pinsker

Andras Pongracz

Abstract

For $n\geq 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 $\Gamma$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\Gamma$ either is 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.

Citation

Bodirsky, M., Martin, B., Pinsker, M., & Pongracz, A. (2019). Constraint satisfaction problems for reducts of homogeneous graphs. SIAM Journal on Computing, 48(4), 1224-1264. https://doi.org/10.1137/16m1082974

Journal Article Type	Article
Acceptance Date	May 2, 2019
Online Publication Date	Jul 18, 2019
Publication Date	Jan 1, 2019
Deposit Date	Jul 2, 2019
Publicly Available Date	Oct 8, 2019
Journal	SIAM Journal on Computing
Print ISSN	0097-5397
Electronic ISSN	1095-7111
Publisher	Society for Industrial and Applied Mathematics
Peer Reviewed	Peer Reviewed
Volume	48
Issue	4
Pages	1224-1264
DOI	https://doi.org/10.1137/16m1082974