Dichotomy for Digraph Homomorphism Problems

We consider the problem of finding a homomorphism from an input digraph G to a fixed digraph H. We show that if H admits a weak-near-unanimity polymorphism $\phi$ then deciding whether G admits a homomorphism to H (HOM(H)) is polynomial time solvable. This confirms the conjecture of Bulatov, Jeavons, and Krokhin, in the form postulated by Maroti and McKenzie, and consequently implies the validity of the celebrated dichotomy conjecture due to Feder and Vardi. We transform the problem into an instance of the list homomorphism problem where initially all the lists are full (contain all the vertices of H). Then we use the polymorphism $\phi$ as a guide to reduce the lists to singleton lists, which yields a homomorphism if one exists.