Digraph homomorphism problem and weak near unanimity polymorphism

Tomas Feder, Jeff Kinne, Ashwin Murali +1

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 $\varphi$ then deciding…