论文标题
具有非负重的有限度图同态同态的二分法
A dichotomy for bounded degree graph homomorphisms with nonnegative weights
论文作者
论文摘要
我们考虑计算由对称矩阵$ a $定义的加权图同构的复杂性。每个对称矩阵$ a $定义图形同构函数$ z_a（\ cdot）$，也称为分区函数。 Dyer and Greenhill [10]建立了对称$ \ {0，1 \} $ - 矩阵$ a $的复杂性二分法（\ cdot）$，他们进一步证明了其＃p-hardness零件也适用于有限度图。 Bulatov和Grohe [4]将Dyer-Greenhill二分法扩展到非负对称矩阵$ a $。但是，它们的硬度证明需要任意大小的图表，并且可以扩展染料绿色二分法的有限程度部分是否可以扩展为15年。我们解决了这个空旷的问题，并证明对于非负对称$ a $，$ z_a（g）$都是在所有图表$ g $的多项式时间内，或者是有限度（和简单）图$ g $的＃p-hard。我们进一步扩展了复杂性二分法，以包括非负顶点重量。此外，我们证明了Goldberg等人的二分法的＃p-毛线部分。 [12]对于$ z_a（\ cdot）$也适用于简单图形，其中$ 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.
