On the complexity of H-coloring for special oriented trees

Abstract

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.

Keywords

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