Counting homomorphisms to K4-minor-free graphs, modulo 2
We study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph H and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the prob...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2021
|
| _version_ | 1826284578450440192 |
|---|---|
| author | Focke, J Goldberg, LA Roth, M Zivny, S |
| author_facet | Focke, J Goldberg, LA Roth, M Zivny, S |
| author_sort | Focke, J |
| collection | OXFORD |
| description | We study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph H and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class ⊕P of parity problems.
We verify their conjecture for all graphs H that exclude the complete graph on 4 vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the ⊕P-complete cases, assuming the randomised Exponential Time Hypothesis.
Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph H. Using this, we subsume all prior progress towards resolving the conjecture (Faben and Jerrum [ToC'15]; Göbel, Goldberg and Richerby [ToCT'14,'16]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2. |
| first_indexed | 2024-03-07T01:15:57Z |
| format | Conference item |
| id | oxford-uuid:8eac9c3f-d3dc-487d-b3e9-03a4d4c66161 |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:15:57Z |
| publishDate | 2021 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:8eac9c3f-d3dc-487d-b3e9-03a4d4c661612022-03-26T22:59:21ZCounting homomorphisms to K4-minor-free graphs, modulo 2Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:8eac9c3f-d3dc-487d-b3e9-03a4d4c66161EnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2021Focke, JGoldberg, LARoth, MZivny, SWe study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph H and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class ⊕P of parity problems. We verify their conjecture for all graphs H that exclude the complete graph on 4 vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the ⊕P-complete cases, assuming the randomised Exponential Time Hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph H. Using this, we subsume all prior progress towards resolving the conjecture (Faben and Jerrum [ToC'15]; Göbel, Goldberg and Richerby [ToCT'14,'16]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2. |
| spellingShingle | Focke, J Goldberg, LA Roth, M Zivny, S Counting homomorphisms to K4-minor-free graphs, modulo 2 |
| title | Counting homomorphisms to K4-minor-free graphs, modulo 2 |
| title_full | Counting homomorphisms to K4-minor-free graphs, modulo 2 |
| title_fullStr | Counting homomorphisms to K4-minor-free graphs, modulo 2 |
| title_full_unstemmed | Counting homomorphisms to K4-minor-free graphs, modulo 2 |
| title_short | Counting homomorphisms to K4-minor-free graphs, modulo 2 |
| title_sort | counting homomorphisms to k4 minor free graphs modulo 2 |
| work_keys_str_mv | AT fockej countinghomomorphismstok4minorfreegraphsmodulo2 AT goldbergla countinghomomorphismstok4minorfreegraphsmodulo2 AT rothm countinghomomorphismstok4minorfreegraphsmodulo2 AT zivnys countinghomomorphismstok4minorfreegraphsmodulo2 |