Zeros of Holant problems: locations and algorithms
Zeros of Holant problems: locations and algorithms
复制标题
Holant 问题的零点：位置和算法
DOI：
10.1145/3418056
复制
发表时间：
2021
影响因子：
1.3
通讯作者：
Zhang Chihao
中科院分区：
文献类型：
--
作者：
Guo Heng;Liao Chao;Lu Pinyan;Zhang Chihao
我们提出了 Holant 问题的完全多项式时间（确定性或随机化）近似方案，该方案由在一些特殊情况下满足广义二阶递推模的非负约束函数定义。因此，三次图上的任何非负 Holant 问题都具有有效的近似算法，除非该问题相当于近似计算完美匹配（该领域的中心开放问题）。这与立方图上的二态自旋系统显示的计算相变形成鲜明对比。我们的主要技术是最近在图多项式零点和近似计数之间建立的联系。
We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second-order recurrence modulo in a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by two-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting.