Counting homomorphisms to square-free graphs, modulo 2

Journal article

We study the problem HomsToH of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph H. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact (non-modular) counting, so subtle dichotomy theorems can arise. We show the following dichotomy: for any H that contains no 4-cycles, HomsToH is either in polynomial time or is P-complete. This partially confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of tree-width-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs including graphs of unbounded tree-width. In particular, we focus on square-free graphs, which are graphs without 4-cycles. These graphs arise frequently in combinatorics, for example in connection with the strong perfect graph theorem and in certain graph algorithms. Previous dichotomy theorems required the graph to be tree-like so that tree-like decompositions could be exploited in the proof. We prove the conjecture for a much richer class of graphs by adopting a much more general approach.

Authors: Goldberg, L; Richerby, D; Goebel, A

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Computation Theory
• Volume: 8
• Issue: 3
• Pages: 12
• Publication date: 2016-05-25
• DOI: 10.1145/2898441
• EISSN: 1942-3462
• ISSN: 1942-3454
• Keywords: Algorithms; Counting modulo 2; Graph homomorphism; Parity complexity dichotomy; Theory