Counting Homomorphisms to Square-Free Graphs, Modulo 2Report as inadecuate

Counting Homomorphisms to Square-Free Graphs, Modulo 2 - Download this document for free, or read online. Document in PDF available to download.

Reference: Andreas Gobel, Leslie Ann Goldberg and David Richerby, Counting Homomorphisms to Square-Free Graphs, Modulo 2.Citable link to this page:


Counting Homomorphisms to Square-Free Graphs, Modulo 2 Series: Leibniz International Proceedings in Informatics

Abstract: 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, 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.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher versionNotes:Copyright Andreas Gobel, Leslie Ann Goldberg, and David Richerby; licensed under Creative Commons License CC-BY. 31st Symposium on Theoretical Aspects of Computer Science (STACS’14). Editors: Ernst W. Mayr and Natacha Portier; pp. 350–361 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

Bibliographic Details

Publisher: Schloss Dagstuhl - LZI GmbH

Publisher Website:

Series:Leibniz International Proceedings in InformaticsIdentifiers


Urn: uuid:faa83d8f-b005-4e89-9cb4-2fe75a4da741 Item Description

Type: Conference item;

Language: en

Version: Publisher version Tiny URL: ora:11220


Author: Andreas Gobel - institutionUniversity of Oxford facultyMathematical,Physical and Life Sciences Division - Computer Science,Depart



Related documents