English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools annual

Global: Zendy Free Plan

Global: Zendy Tools monthly

Global: Zendy Plus monthly

We study the problem of computing the parity of the number of homomorphismsfrom 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, ifsatisfied, the problem is solvable in polynomial time and, otherwise, theproblem is complete for the complexity class $\oplus\mathrm{P}$ of parityproblems. We verify their conjecture for all graphs $H$ that exclude thecomplete graph on $4$ vertices as a minor. Further, we rule out the existenceof a subexponential-time algorithm for the $\oplus\mathrm{P}$-complete cases,assuming the randomised Exponential Time Hypothesis. Our proofs introduce anovel method of deriving hardness from globally defined substructures of thefixed graph $H$. Using this, we subsume all prior progress towards resolvingthe conjecture (Faben and Jerrum [ToC'15]; G\"obel, Goldberg and Richerby[ToCT'14,'16]). As special cases, our machinery also yields a proof of theconjecture for graphs with maximum degree at most $3$, as well as a fullclassification for the problem of counting list homomorphisms, modulo $2$.

Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2