  Counting graph homomorphisms and its generalizations such as the Counting
Constraint Satisfaction Problem (CSP), its variations, and counting problems in
general have been intensively studied since the pioneering work of Valiant.
While the complexity of exact counting of graph homomorphisms (Dyer and
Greenhill, 2000) and the counting CSP (Bulatov, 2013, and Dyer and Richerby,
2013) is well understood, counting modulo some natural number has attracted
considerable interest as well. In their 2015 paper Faben and Jerrum suggested a
conjecture stating that counting homomorphisms to a fixed graph H modulo a
prime number is hard whenever it is hard to count exactly, unless H has
automorphisms of certain kind. In this paper we confirm this conjecture. As a
part of this investigation we develop techniques that widen the spectrum of
reductions available for modular counting and apply to the general CSP rather
than being limited to graph homomorphisms.
