Abstract
For a fixed digraph G, the Constraint Satisfaction Problem with the template G, or CSP(G) for short, is the problem of deciding whether a given input digraph H admits a homomorphism to G. The dichotomy conjecture of Feder and Vardi states that CSP(G), for any choice of 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 39 vertices) defining an NP-complete CSP(G).