Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F16%3A10331277" target="_blank" >RIV/00216208:11320/16:10331277 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.119" target="_blank" >http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.119</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.119" target="_blank" >10.4230/LIPIcs.ICALP.2016.119</a>

Result language
angličtina
Original language name
Constraint Satisfaction Problems for Reducts of Homogeneous Graphs
Original language description
For nGREATER-THAN OR EQUAL TO3 , 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.
Czech name
—
Czech description
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)