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%2F19%3A10402073" target="_blank" >RIV/00216208:11320/19:10402073 - isvavai.cz</a>

Výsledek na webu

<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JyMS-LdgAr" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=JyMS-LdgAr</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1137/16M1082974" target="_blank" >10.1137/16M1082974</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 n &gt;= 3, let (H-n, E) denote the nth 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 F 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.

Název v anglickém jazyce

CONSTRAINT SATISFACTION PROBLEMS FOR REDUCTS OF HOMOGENEOUS GRAPHS

Popis výsledku anglicky

For n &gt;= 3, let (H-n, E) denote the nth 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 F 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2019

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 periodika

SIAM Journal on Computing

ISSN

0097-5397

e-ISSN

—

Svazek periodika

2019

Číslo periodika v rámci svazku

48

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

41

Strana od-do

1224-1264

Kód UT WoS článku

000483940500003

EID výsledku v databázi Scopus

2-s2.0-85072740831