"The complexity of surjective homomorphism problems".
Barnaby Martin

The problem SurHom(B) takes as input a structure A and asks if there
is a surjective homomorphism to B. Remarkably little is known about
the complexity of surjective homomorphism problems in other than
trivial cases. We survey the area, particularly from the perspective
of closely related problems for which some classifications are known.
These related problems, in order of similarity to Surjective
Homomorphism, are Compaction, Retraction and List Homomorphism. While
we give some known classifications for SurHom(B), the central theme of
the talk will be the open complexity of both SurHom(C6) and
SurHom(C*4) [where C*4 is the reflexive 4-cycle]. The compaction
problems Comp(C6) and Comp(C*4) are both NP-complete, but the same
difficulties present when trying to extend the constructions to prove
hardness of SurHom(C6) and SurHom(C*4).