On the complexity of H-coloring for special oriented trees

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F18%3A10383359" target="_blank" >RIV/00216208:11320/18:10383359 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1016/j.ejc.2017.10.001" target="_blank" >https://doi.org/10.1016/j.ejc.2017.10.001</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1016/j.ejc.2017.10.001" target="_blank" >10.1016/j.ejc.2017.10.001</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On the complexity of H-coloring for special oriented trees

Popis výsledku v původním jazyce

For a fixed digraph H, the H -coloring problem is the problem of deciding whether a given input digraph G admits a homomorphism to H. The CSP dichotomy conjecture of Feder and Vardi is equivalent to proving that, for any H, the H-coloring problem is in P or NP -complete. We confirm this dichotomy for a certain class of oriented trees, which we call special trees (generalizing earlier results on special triads and polyads). Moreover, we prove that every tractable special oriented tree has bounded width, i.e., the corresponding H-coloring problem is solvable by local consistency checking. Our proof relies on recent algebraic tools, namely characterization of congruence meet-semidistributivity via pointing operations and absorption theory.

Název v anglickém jazyce

On the complexity of H-coloring for special oriented trees

Popis výsledku anglicky

For a fixed digraph H, the H -coloring problem is the problem of deciding whether a given input digraph G admits a homomorphism to H. The CSP dichotomy conjecture of Feder and Vardi is equivalent to proving that, for any H, the H-coloring problem is in P or NP -complete. We confirm this dichotomy for a certain class of oriented trees, which we call special trees (generalizing earlier results on special triads and polyads). Moreover, we prove that every tractable special oriented tree has bounded width, i.e., the corresponding H-coloring problem is solvable by local consistency checking. Our proof relies on recent algebraic tools, namely characterization of congruence meet-semidistributivity via pointing operations and absorption theory.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2018

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

European Journal of Combinatorics

ISSN

0195-6698

e-ISSN

—

Svazek periodika

2018

Číslo periodika v rámci svazku

69

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

22

Strana od-do

54-75

Kód UT WoS článku

000423886700006

EID výsledku v databázi Scopus

2-s2.0-85042142918