CISPA
Browse
cispa_all_3518.pdf (791.48 kB)

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

Download (791.48 kB)
journal contribution
posted on 2023-11-29, 18:06 authored by Jacob FockeJacob Focke, Leslie Ann Goldberg, Marc Roth, Stanislav Živný
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.

History

Preferred Citation

Jacob Focke, Leslie Goldberg, Marc Roth and Stanislav Živný. Counting Homomorphisms to K4-minor-free Graphs, modulo 2. In: SIAM Journal on Discrete Mathematics. 2021.

Primary Research Area

  • Reliable Security Guarantees

Legacy Posted Date

2021-12-03

Journal

SIAM Journal on Discrete Mathematics

Pages

2749 - 2814

Open Access Type

  • Green

Sub Type

  • Article

BibTeX

@article{cispa_all_3518, title = "Counting Homomorphisms to K4-minor-free Graphs, modulo 2", author = "Focke, Jacob and Goldberg, Leslie Ann and Roth, Marc and Živný, Stanislav", journal="{SIAM Journal on Discrete Mathematics}", year="2021", }

Usage metrics

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC