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 [Theory Comput., 11 (2015), pp. 35--57] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomi...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Society for Industrial and Applied Mathematics
2021
|
| _version_ | 1826276283254833152 |
|---|---|
| author | Focke, J Goldberg, L Roth, M Zivny, S |
| author_facet | Focke, J Goldberg, L 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 [Theory Comput., 11 (2015), pp. 35--57] 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 $\oplus{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on four vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\oplus{P}$-complete cases, assuming the randomized 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 toward resolving the conjecture (Faben and Jerrum [Theory Comput., 11 (2015), pp. 35--57]; Göbel, Goldberg, and Richerby [ACM Trans. Comput. Theory, 6 (2014), 17; ACM Trans. Comput. Theory, 8 (2016), 12]). 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-06T23:11:37Z |
| format | Journal article |
| id | oxford-uuid:65acfe8a-8e8d-46f3-ba02-29dce6cac82e |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-06T23:11:37Z |
| publishDate | 2021 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | oxford-uuid:65acfe8a-8e8d-46f3-ba02-29dce6cac82e2022-03-26T18:26:59ZCounting homomorphisms to K4-minor-free graphs, modulo 2Journal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:65acfe8a-8e8d-46f3-ba02-29dce6cac82eEnglishSymplectic ElementsSociety for Industrial and Applied Mathematics2021Focke, JGoldberg, LRoth, 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 [Theory Comput., 11 (2015), pp. 35--57] 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 $\oplus{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on four vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\oplus{P}$-complete cases, assuming the randomized 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 toward resolving the conjecture (Faben and Jerrum [Theory Comput., 11 (2015), pp. 35--57]; Göbel, Goldberg, and Richerby [ACM Trans. Comput. Theory, 6 (2014), 17; ACM Trans. Comput. Theory, 8 (2016), 12]). 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, L 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 goldbergl countinghomomorphismstok4minorfreegraphsmodulo2 AT rothm countinghomomorphismstok4minorfreegraphsmodulo2 AT zivnys countinghomomorphismstok4minorfreegraphsmodulo2 |