Research Repository

Counting Homomorphisms to Square-Free Graphs, Modulo 2

Göbel, Andreas and Goldberg, Leslie Ann and Richerby, David (2016) 'Counting Homomorphisms to Square-Free Graphs, Modulo 2.' ACM Transactions on Computation Theory, 8 (3). 1 - 29. ISSN 1942-3454

GGR2016-Homs_mod_2.pdf - Accepted Version

Download (443kB) | Preview


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 (nonmodular) counting; thus, 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.

Item Type: Article
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Elements
Date Deposited: 23 Jul 2021 07:20
Last Modified: 23 Jul 2021 08:15

Actions (login required)

View Item View Item