A Simple Algorithm for Sampling Colorings of G(n, d/n) Up to The Gibbs Uniqueness Threshold
A Simple Algorithm for Sampling Colorings of G(n, d/n) Up to The Gibbs Uniqueness Threshold
复制标题
一种对 G(n, d/n) 染色进行采样直至吉布斯唯一性阈值的简单算法
DOI：
10.1137/140977643
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
C. Efthymiou
中科院分区：
文献类型：
--
作者：
C. Efthymiou
图的近似随机着色问题是计算机科学和统计物理学中研究较多的问题。它相当于构造了一个在多项式时间内分布接近Gibbs分布的a-着色。在这里，我们讨论了当基础图是ERDÖS的实例时的问题--Rényi随机图，其中有一个足够大的常数。我们提出了一种新的高效的近似随机着色算法。更具体地说，在概率至少超过输入实例和For的情况下，该算法返回分布在输入图实例的Gibbs分布的总变化距离内的着色。我们提出的算法既不是马尔可夫链蒙特卡罗算法，也不是受统计物理学家提出的消息传递算法的启发。大体上，这个想法是这样的。最初，我们删除了足够多的输入图的边。这会产生一个可以有效地随机上色的“简单图形”。该算法随机给这个简单的图形上色。然后，它将被移除的边逐个放回原处。每次放回一条新的边时，算法都会更新图形的着色，以便着色保持随机。该算法的性能在很大程度上依赖于Gibbs分布的某些空间相关衰减特性。
Approximate random-coloring of a graphis a well-studied problem in computer science and statistical physics. It amounts to constructing a-coloring ofwhich is distributed close to theGibbs distributionin polynomial time. Here, we deal with the problem when the underlying graph is an instance of the Erdös--Rényi random graph, whereis a sufficiently large constant. We propose a novel efficient algorithm for approximate random-coloringfor any. To be more specific, with probability at leastover the input instancesand for, the algorithm returns a-coloring which is distributed within total variation distancefrom the Gibbs distribution of the input graph instance. The algorithm we propose is neither Markov chain Monte Carlo nor inspired by the message-passing algorithms proposed by statistical physicists. Roughly, the idea is as follows. Initially we remove sufficiently many edges of the input graph. This results in a “simple graph” which can be-colored randomly efficiently. The algorithm colors randomly this simple graph. Then it puts back the removed edges one by one. Every time a new edge is put back the algorithm updates the coloring of the graph so that the coloring remains random. The performance of the algorithm depends heavily on certain spatial correlation decay properties of the Gibbs distribution.