On the complexity of H-coloring for special oriented trees

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
On the complexity of H-coloring for special oriented trees
Original language description
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.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)