A dichotomy for bounded degree graph homomorphisms with nonnegative weights
A dichotomy for bounded degree graph homomorphisms with nonnegative weights
复制标题
DOI：
10.4230/lipics.icalp.2020.66
复制
发表时间：
2020-02
期刊：
影响因子：
--
通讯作者：
A. Govorov;Jin-Yi Cai;Martin E. Dyer
中科院分区：
文献类型：
--
作者：
A. Govorov;Jin-Yi Cai;Martin E. Dyer
考虑由对称矩阵a定义的加权图同态计数的复杂性。每个对称矩阵$A$定义了一个图同态函数$Z_A(\cdot)$，也称为配分函数。Dyer和Greenhill[10]建立了对称矩阵$Z_A(\cdot)$的复杂度二分法$Z_A(\cdot)$，并进一步证明了其# p -硬度部分也适用于有界度图。Bulatov和Grohe[4]将Dyer-Greenhill二分法推广到非负对称矩阵$A$。然而，它们的硬度证明需要任意大度的图，并且Dyer-Greenhill二分法的有界度部分是否可以推广，这是15年来的一个开放问题。我们解决了这个开放问题，并证明了对于非负对称的$A$, $Z_A(G)$对于所有图$G$都是多项式时间，或者对于有界次（和简单）图$G$是# p -困难的。我们进一步扩展了复杂度二分法，使其包含非负的顶点权值。此外，我们证明了Goldberg et al.[12]对$Z_A(\cdot)$的二分法的# p -硬度部分也适用于简单图，其中$A$是任何实对称矩阵。
We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix $A$. Each symmetric matrix $A$ defines a graph homomorphism function $Z_A(\cdot)$, also known as the partition function. Dyer and Greenhill [10] established a complexity dichotomy of $Z_A(\cdot)$ for symmetric $\{0, 1\}$-matrices $A$, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [4] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices $A$. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric $A$, either $Z_A(G)$ is in polynomial time for all graphs $G$, or it is #P-hard for bounded degree (and simple) graphs $G$. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for $Z_A(\cdot)$ also holds for simple graphs, where $A$ is any real symmetric matrix.