Bodirsky, Manuel and Martin, Barnaby and Pinsker, Michael and Pongracz, Andras (2019) 'Constraint satisfaction problems for reducts of homogeneous graphs.', SIAM journal of computing., 48 (4). pp. 1224-1264.
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.
|Full text:||Publisher-imposed embargo |
(AM) Accepted Manuscript
File format - PDF (558Kb)
|Full text:||(VoR) Version of Record|
Download PDF (540Kb)
|Publisher Web site:||https://doi.org/10.1137/16M1082974|
|Publisher statement:||© 2019 Society for Industrial and Applied Mathematics.|
|Date accepted:||02 May 2019|
|Date deposited:||02 July 2019|
|Date of first online publication:||18 July 2019|
|Date first made open access:||08 October 2019|
Save or Share this output
|Look up in GoogleScholar|