论文标题
计数同构为$ k_4 $ -minor-fime图，Modulo 2
Counting Homomorphisms to $K_4$-minor-free Graphs, modulo 2
论文作者
论文摘要
我们研究了计算从输入图$ g $到固定图$ h $的同态数量均衡的问题。 Faben和Jerrum [TOC'15]在图$ H $上引入了一个明确的标准，并推测，如果满足，则可以在多项式时间内解决问题，否则，对于复杂性类别$ \ oplus \ oplus \ mathrm {p}的问题是完全问题的问题。我们验证了他们对所有图形$ h $的猜想，这些图表不包括$ 4 $顶点的完整图。此外，我们排除存在$ \ oplus \ mathrm {p} $的次指数时间算法的存在，假设是随机指数时间假设。我们的证明引入了一种新颖的方法，可以从固定图$ H $的全球定义子结构中得出硬度。使用它，我们将所有先前的进步都归为解决猜想（Faben和Jerrum [Toc'15]；Göbel，Goldberg和Richerby [Toct'14，'16]）。作为特殊情况，我们的机器还提供了最高学位的图表的猜想证明，以及对计数列表同构同构的问题的完整分类，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 $\oplus\mathrm{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 $\oplus\mathrm{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$.
