Corelab Seminar

Andreas Goebel
Modular Counting and Graph Homomorphisms

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 where counting modulo~$2$, is intractable. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (non-modular) counting. 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 in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. Modular counting provides a rich setting in which to study the structure of homomorphism problems. In this talk we will discuss the complexity of counting graph homomorphisms modulo 2. Faben and Jerrum are the first to study the complexity of counting graph homomorphisms modulo~$2$. They show that for a specific family of target graphs the problem of counting homomorphisms to a graph modulo~2 is computationally easy and conjecture that for every other target graph the problem is computationally hard. They also prove their conjecture when $H$ is a tree. Our results build upon the work of Faben and Jerrum. We first give a dichotomy theorem for the class of cactus graphs, which are connected graphs in which every edge belongs to at most one cycle. We also confirm the conjecture of Faben and Jerrum for all graphs that contain no 4-cycles.