  A homomorphism from a graph G to a graph H is a function from V(G) to V(H)
that preserves edges. Many combinatorial structures that arise in mathematics
and computer science can be represented naturally as graph homomorphisms and as
weighted sums of graph homomorphisms. In this paper, we study the complexity of
counting homomorphisms modulo 2. The complexity of modular counting was
introduced by Papadimitriou and Zachos and it has been pioneered by Valiant who
famously introduced a problem for which counting modulo 7 is easy but counting
modulo 2 is intractable. Modular counting provides a rich setting in which to
study the structure of homomorphism problems. In this case, the structure of
the graph H has a big influence on the complexity of the problem. Thus, our
approach is graph-theoretic. We give a complete solution for the class of
cactus graphs, which are connected graphs in which every edge belongs to at
most one cycle. Cactus graphs arise in many applications such as the modelling
of wireless sensor networks and the comparison of genomes. We show that, for
some cactus graphs H, counting homomorphisms to H modulo 2 can be done in
polynomial time. For every other fixed cactus graph H, the problem is complete
for the complexity class parity-P which is a wide complexity class to which
every problem in the polynomial hierarchy can be reduced (using randomised
reductions). Determining which H lead to tractable problems can be done in
polynomial time. Our result builds upon the work of Faben and Jerrum, who gave
a dichotomy for the case in which H is a tree.
