CSP dichotomy for special triads
Libor Barto, Marcin Kozik, Miklós Maróti, Todd Niven · Proceedings of the American Mathematical Society · 2009
For a fixed digraph G \mathbb {G} , the Constraint Satisfaction Problem with the template G \mathbb {G} , or C S P ( G ) \mathrm {CSP}(\mathbb {G}) for short, is the problem of deciding whether a given input digraph H \mathbb {H} admits a homomorphism to G \mathbb {G} . The dichotomy conjecture of Feder and Vardi states that C S P ( G ) \mathrm {CSP}(\mathbb {G}) , for any choice of G \mathbb G , is solvable in polynomial time or NP-complete. This paper confirms the conjecture for a class of oriented trees called special triads. As a corollary we get the smallest known example of an oriented tree (with 33 33 vertices) defining an NP-complete C S P ( G ) \mathrm {CSP}(\mathbb {G}) .