Counting homomorphisms to square-free graphs, modulo 2
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 (non-modular) counting, so subtle dichotomy...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Association for Computing Machinery
2016
|
| _version_ | 1826259056692559872 |
|---|---|
| author | Goldberg, L Richerby, D Goebel, A |
| author_facet | Goldberg, L Richerby, D Goebel, A |
| author_sort | Goldberg, L |
| collection | OXFORD |
| description | 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 (non-modular) 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 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. |
| first_indexed | 2024-03-06T18:43:51Z |
| format | Journal article |
| id | oxford-uuid:0dd1c6c8-5e47-4c22-b574-f5662f821a3b |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:43:51Z |
| publishDate | 2016 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:0dd1c6c8-5e47-4c22-b574-f5662f821a3b2022-03-26T09:42:35ZCounting homomorphisms to square-free graphs, modulo 2Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:0dd1c6c8-5e47-4c22-b574-f5662f821a3bSymplectic Elements at OxfordAssociation for Computing Machinery2016Goldberg, LRicherby, DGoebel, AWe 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 (non-modular) 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 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. |
| spellingShingle | Goldberg, L Richerby, D Goebel, A 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 goldbergl countinghomomorphismstosquarefreegraphsmodulo2 AT richerbyd countinghomomorphismstosquarefreegraphsmodulo2 AT goebela countinghomomorphismstosquarefreegraphsmodulo2 |