Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2
| Autor: | Jacob Focke, Marc Roth, Stanislav Živný, Leslie Ann Goldberg |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
Discrete mathematics
FOS: Computer and information sciences F.2.2 G.2.1 Discrete Mathematics (cs.DM) General Mathematics Modulo 010102 general mathematics Minor (linear algebra) 0102 computer and information sciences Computational Complexity (cs.CC) 01 natural sciences Graph Combinatorics Computer Science - Computational Complexity 010201 computation theory & mathematics Homomorphism 0101 mathematics Parity (mathematics) Computer Science - Discrete Mathematics Mathematics |
| Zdroj: | Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) |
| DOI: | 10.48550/arxiv.2006.16632 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|