Counting Homomorphisms to K4-minor-free Graphs, modulo 2

Focke, Jacob and Goldberg, Leslie Ann and Roth, Marc and Živný, Stanislav
(2021) Counting Homomorphisms to K4-minor-free Graphs, modulo 2.
SIAM Journal on Discrete Mathematics, 35 (4). pp. 2749-2814. ISSN 0895-4801

[img]
Preview
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.

Actions

Actions (login required)

View Item View Item