Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Constraint Satisfaction Problems for Reducts of Homogeneous Graphs

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název statě ve sborníku

Leibniz international proceedings in informatics

ISBN

978-3-95977-013-2

ISSN

1868-8969

e-ISSN

—

Počet stran výsledku

14

Strana od-do

1-14

Název nakladatele

Dagstuhl Publishing

Místo vydání

Německo

Místo konání akce

Roma, Itálie

Datum konání akce

12. 7. 2016

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—