Constraint satisfaction problems for reducts of homogeneous graphs

Bodirsky, Manuel and Martin, Barnaby and Pinsker, Michael and Pongrácz, András (2019) Constraint satisfaction problems for reducts of homogeneous graphs. SIAM JOURNAL ON COMPUTING, 48 (4). pp. 1224-1264. ISSN 0097-5397

Preview

Text graphCSPs.pdf - Submitted Version Available under License Creative Commons Attribution. Download (397kB) | Preview

Abstract

Let H_n 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 F with domain the same as that of H_n whose relations are first-order definable in H_n the constraint satisfaction problem for F 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

Item Type:	Article
Subjects:	Q Science / természettudomány > QA Mathematics / matematika > QA75 Electronic computers. Computer science / számítástechnika, számítógéptudomány
Depositing User:	Dr. András Pongrácz
Date Deposited:	12 Sep 2020 17:13
Last Modified:	03 Apr 2023 06:54
URI:	http://real.mtak.hu/id/eprint/113102

Available Versions of this Item

• Constraint satisfaction problems for reducts of homogeneous graphs. (deposited 25 Sep 2018 08:31)
  • Constraint satisfaction problems for reducts of homogeneous graphs. (deposited 12 Sep 2020 17:13) [Currently Displayed]

Actions (login required)

Edit Item