Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
This provides a more efficient and parallelizable method for exact uniform sampling in graph theory, with potential applications in statistical physics and computer science, though it is incremental as it builds on existing partial rejection sampling and CFTP methods.
The paper tackles the problem of uniformly sampling proper graph colorings by introducing a new algorithm based on partial rejection sampling and a soft relaxation technique, achieving a runtime of O(L^{log* n}·nΔ) and conjecturing linear-time parallelizability for general graphs.
We present a new algorithm for the exact uniform sampling of proper \(k\)-colorings of a graph on \(n\) vertices with maximum degree~\(Î\). The algorithm is based on partial rejection sampling (PRS) and introduces a soft relaxation of the proper coloring constraint that is progressively tightened until an exact sample is obtained. Unlike coupling from the past (CFTP), the method is inherently parallelizable. We propose a hybrid variant that decomposes the global sampling problem into independent subproblems of size \(O(\log n)\), each solved by any existing exact sampler. This decomposition acts as a {\em complexity reducer}: it replaces the input size~\(n\) with \(O(\log n)\) in the component solver's runtime, so that any improvement in direct methods automatically yields a stronger result. Using an existing CFTP method as the component solver, this improves upon the best known exact sampling runtime for \(k>3Î\). Recursive application of the hybrid drives the runtime to \(O(L^{\log^* n}\cdot nÎ)\), where \(L\) is the number of relaxation levels. We conjecture that \(L\) is bounded independently of~\(n\), which would yield a linear-time parallelizable algorithm for general graphs. Our simulations strongly support this conjecture.