A Deterministic Algorithm for Counting Colorings with 2-Delta Colors
A Deterministic Algorithm for Counting Colorings with 2-Delta Colors
复制标题
DOI：
10.1109/focs.2019.00085
复制
发表时间：
2019-06
期刊：
影响因子：
--
通讯作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
中科院分区：
文献类型：
--
作者：
Jingcheng Liu;A. Sinclair;P. Srivastava
我们给出了一个多项式时间确定性近似算法(A FPTAS)，用于计算最大度为Delta的图的q-染色的个数，仅当Q≥2Delta时。这大大改进了以前解决该问题的确定性算法，其中最好的算法需要Q≥2.58增量，并与通过直接应用马尔科夫链蒙特卡罗获得的随机算法的自然界相匹配。在图也是无三角形的情况下，我们证明了我们的算法适用于较弱的条件Q≥α∆+β，其中α≈1.764和β=β(α)是绝对常数。我们的结果更普遍地适用于列表着色和反铁磁Potts模型的配分函数。我们论证的核心是在复平面上建立一个Potts模型配分函数(经典的图多项式)没有零点的区域。这一结果大大加强了之前关于同一问题的工作，具有独立的利益。我们的算法通过Barvinok的“多项式内插”方法立即从零点开始。有趣的是，我们识别零点区域的方法利用了马尔可夫链分析中使用的概率和组合思想。
We give a polynomial time deterministic approximation algorithm (an FPTAS) for counting the number of q-colorings of a graph of maximum degree Delta, provided only that q ≥ 2Delta. This substantially improves on previous deterministic algorithms for this problem, the best of which requires q ≥ 2.58Delta, and matches the natural bound for randomized algorithms obtained by a straightforward application of Markov chain Monte Carlo. In the case when the graph is also triangle-free, we show that our algorithm applies under the weaker condition q ≥ α∆+β, where α ≈ 1.764 and β = β(α) are absolute constants. Our result applies more generally to list colorings, and to the partition function of the anti-ferromagnetic Potts model. The core of our argument is the establishment of a region in the complex plane in which the Potts model partition function (a classical graph polynomial) has no zeros. This result, which substantially sharpens previous work on the same problem, is of independent interest. Our algorithms follow immediately from zero-freeness via the “polynomial interpolation" method of Barvinok. Interestingly, our method for identifying the zero-free region leverages probabilistic and combinatorial ideas that have been used in the analysis of Markov chains.