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 [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.

A full version of our paper, containing all proofs, is available at https://arxiv.org/abs/ 2006.16632 and is attached as an appendix. Here we number key lemmas to match the numbering in the full version.