Portal de Periódicos da CAPES

Counting Homomorphisms to Square-Free Graphs, Modulo 2

2015; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-662-47672-7_52

1611-3349

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

Markov Chains and Monte Carlo Methods

We study the problem $$\oplus \textsc {HomsTo}{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 (non-modular) counting, so subtle dichotomy theorems can arise. We show the following dichotomy: for any H that contains no 4-cycles, $$\oplus \textsc {HomsTo}{H}$$ is either in polynomial time or is $$\oplus \mathrm {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.