论文标题
二分法，用于在有界度图上具有复杂值的同态同构的二分法
Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
论文作者
论文摘要
图同态的复杂性一直是一项激烈研究的主题[11，12，42，21，17，6，20]。分区函数$ z _ {\ mathbf a}（\ cdot）$ of Graph同态由对称矩阵$ \ mathbf a $ over $ \ mathbb c $定义。我们证明[6]的复杂性二分法延伸至有限程度图。更确切地说，我们证明，每$ g $的$ g \ mapsto z _ {\ mathbf a}（g）$是可以在多项式时间内计算的，或者对于某些$δ> 0 $，它是＃p-hard for（simple）图形$ g $，带有最大程度$δ（g）（g）\leΔ$。此二分法的$ \ mathbf $ $ a $的障碍性标准是明确的，可以在多项式时间内以$ \ mathbf a $的规模确定。我们还表明，二分法是有效的，因为在各自情况下，可以从$ \ mathbf a $中构建$ z {\ mathbf a} $ z _ {\ mathbf a}（\ cdot）$的p-time算法。
The complexity of graph homomorphisms has been a subject of intense study [11, 12, 4, 42, 21, 17, 6, 20]. The partition function $Z_{\mathbf A}(\cdot)$ of graph homomorphism is defined by a symmetric matrix $\mathbf A$ over $\mathbb C$. We prove that the complexity dichotomy of [6] extends to bounded degree graphs. More precisely, we prove that either $G \mapsto Z_{\mathbf A}(G)$ is computable in polynomial-time for every $G$, or for some $Δ> 0$ it is #P-hard over (simple) graphs $G$ with maximum degree $Δ(G) \le Δ$. The tractability criterion on $\mathbf A$ for this dichotomy is explicit, and can be decided in polynomial-time in the size of $\mathbf A$. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, $Z_{\mathbf A}(\cdot)$ can be constructed from $\mathbf A$, in the respective cases.
