Counting Homomorphisms to $K_4$-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 pro...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2020
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2006.16632 http://arxiv.org/abs/2006.16632 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | 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 $\oplus\mathrm{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 $\oplus\mathrm{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$. |
|---|---|
| DOI: | 10.1137/20M1382921 |