Title: Surjective H-Colouring over Reflexive Digraphs,
Abstract: The Surjective H-Colouring problem is to test if a given graph allows a
vertex-surjective homomorphism to a fixed graph H. The complexity of this
problem has been well studied for undirected (partially) reflexive graphs. We
introduce endo-triviality, the property of a structure that all of its
endomorphisms that do not have range of size 1 are automorphisms, as a means to
obtain complexity-theoretic classifications of Surjective H-Colouring in the
case of reflexive digraphs.
Chen [2014] proved, in the setting of constraint satisfaction problems, that
Surjective H-Colouring is NP-complete if H has the property that all of its
polymorphisms are essentially unary. We give the first concrete application of
his result by showing that every endo-trivial reflexive digraph H has this
property. We then use the concept of endo-triviality to prove, as our main
result, a dichotomy for Surjective H-Colouring when H is a reflexive
tournament: if H is transitive, then Surjective H-Colouring is in NL, otherwise
it is NP-complete.
By combining this result with some known and new results we obtain a
complexity classification for Surjective H-Colouring when H is a partially
reflexive digraph of size at most 3.