Title: The Complexity of Counting Surjective Homomorphisms and Compactions,
Abstract: A homomorphism from a graph G to a graph H is a function from the vertices of
G to the vertices of H that preserves edges. A homomorphism is surjective if it
uses all of the vertices of H and it is a compaction if it uses all of the
vertices of H and all of the non-loop edges of H. Hell and Nesetril gave a
complete characterisation of the complexity of deciding whether there is a
homomorphism from an input graph G to a fixed graph H. A complete
characterisation is not known for surjective homomorphisms or for compactions,
though there are many interesting results. Dyer and Greenhill gave a complete
characterisation of the complexity of counting homomorphisms from an input
graph G to a fixed graph H. In this paper, we give a complete characterisation
of the complexity of counting surjective homomorphisms from an input graph G to
a fixed graph H and we also give a complete characterisation of the complexity
of counting compactions from an input graph G to a fixed graph H. In an
addendum we use our characterisations to point out a dichotomy for the
complexity of the respective approximate counting problems (in the connected
case).