(2021) Counting Homomorphisms to K4-minor-free Graphs, modulo 2.
|
Text
20m1382921.pdf Download (810kB) | Preview |
Abstract
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.
| Item Type: | Article |
|---|---|
| Divisions: | Dániel Marx (DM) |
| Depositing User: | Jacob Focke |
| Date Deposited: | 03 Dec 2021 09:01 |
| Last Modified: | 03 Dec 2021 09:01 |
| Primary Research Area: | NRA2: Reliable Security Guarantees |
| URI: | https://publications.cispa.saarland/id/eprint/3518 |
Actions
Actions (login required)
 |
View Item |