Counting Homomorphisms to Square-Free Graphs, Modulo 2
We study the problem ⊕HomsTo<em>H</em> of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph <em>H</em>. A characteristic feature of modular counting is that cancellations make wider classes of instances tractable than is the case for exact...
| Autores principales: | , , |
|---|---|
| Formato: | Conference item |
| Lenguaje: | English |
| Publicado: |
Schloss Dagstuhl - LZI GmbH
2015
|
| _version_ | 1826306262707470336 |
|---|---|
| author | Gobel, A Goldberg, L Richerby, D |
| author_facet | Gobel, A Goldberg, L Richerby, D |
| author_sort | Gobel, A |
| collection | OXFORD |
| description | We study the problem ⊕HomsTo<em>H</em> of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph <em>H</em>. 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 <em>H</em> that contains no 4-cycles, ⊕HomsTo<em>H</em> 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. |
| first_indexed | 2024-03-07T06:45:17Z |
| format | Conference item |
| id | oxford-uuid:faa83d8f-b005-4e89-9cb4-2fe75a4da741 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T06:45:17Z |
| publishDate | 2015 |
| publisher | Schloss Dagstuhl - LZI GmbH |
| record_format | dspace |
| spelling | oxford-uuid:faa83d8f-b005-4e89-9cb4-2fe75a4da7412022-03-27T13:07:44ZCounting Homomorphisms to Square-Free Graphs, Modulo 2Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:faa83d8f-b005-4e89-9cb4-2fe75a4da741EnglishOxford University Research Archive - ValetSchloss Dagstuhl - LZI GmbH2015Gobel, AGoldberg, LRicherby, DWe study the problem ⊕HomsTo<em>H</em> of counting, modulo 2, the homomorphisms from an input graph to a fixed undirected graph <em>H</em>. 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 <em>H</em> that contains no 4-cycles, ⊕HomsTo<em>H</em> 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. |
| spellingShingle | Gobel, A Goldberg, L Richerby, D Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
| title | Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
| title_full | Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
| title_fullStr | Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
| title_full_unstemmed | Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
| title_short | Counting Homomorphisms to Square-Free Graphs, Modulo 2 |
| title_sort | counting homomorphisms to square free graphs modulo 2 |
| work_keys_str_mv | AT gobela countinghomomorphismstosquarefreegraphsmodulo2 AT goldbergl countinghomomorphismstosquarefreegraphsmodulo2 AT richerbyd countinghomomorphismstosquarefreegraphsmodulo2 |