The complexity of counting surjective homomorphisms and compactions

Conference item

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 Neˇsetˇril 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.

Authors: Focke, J; Goldberg, L; Zivny, S

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Society for Industrial and Applied Mathematics
• Host title: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms
• Journal: ACM-SIAM Symposium on Discrete Algorithms
• Publication date: 2017-01-01
• Acceptance date: 2017-09-29
• DOI: 10.1137/1.9781611975031.116
• ISBN: 9781611975031