On the complexity of H-coloring for special oriented trees

Abstrakt

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.

Klíčová slova

• constraint satisfaction problems
• csp dichotomy
• bounded width
• homomorphisms
• algebras