Title: Dichotomy for Digraph Homomorphism Problems (two algorithms),
Abstract: Update : An issue has been found in the correctness of our algorithm, and we
are working to resolve the issue. Until a resolution is found, we retract our
main claim that our approach gives a combinatorial solution to the CSP
conjecture. We remain hopeful that we can resolve the issues. We thank Ross
Willard for carefully checking the algorithm and pointing out the mistake in
the version of this manuscript. We briefly explain one issue at the beginning
of the text, and leave the rest of the manuscript intact for the moment . Ross
Willard is posting a more involved description of a counter-example to the
algorithm in the present manuscript. We have an updated manuscript that
corrects some issues while still not arriving at a full solution; we will keep
this private as long as unresolved issues remain.
Previous abstract : 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 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.