2015/01/29 by Göbel, Andreas, Goldberg, Leslie Ann, Richerby, David · 1 citation
#Combinatorics (math.CO) #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1501.07539
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 confirms a conjecture of Faben and Jerrum that was previously only known to hold for trees and for a restricted class of treewidth-2 graphs called cactus graphs. We confirm the conjecture for a rich class of graphs including graphs of unbounded treewidth. 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.