Portal de Periódicos da CAPES

Counting Homomorphisms to Square-Free Graphs, Modulo 2

2016; Association for Computing Machinery; Volume: 8; Issue: 3 Linguagem: Inglês

10.1145/2898441

1942-3462

Andreas Göbel, Leslie Ann Goldberg, David Richerby,

Limits and Structures in Graph Theory

We study the problem ⊕H oms T o H 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 (nonmodular) counting; thus, subtle dichotomy theorems can arise. We show the following dichotomy: for any H that contains no 4-cycles, ⊕H oms T o H 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.