The Complexity of Counting Surjective Homomorphisms and Compactions

Jacob Focke, Leslie Ann Goldberg, Stanislav Zivny

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 vertic…