Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling

Abstract

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.

arXiv commentWithdrawn by the author Sarat Moka: the proof of Theorem 2 is incorrect. The resampling set constructed in Section 4 is not that of the general partial rejection sampling algorithm of Guo, Jerrum and Liu (STOC 2017), so their Theorem 4.5 does not apply and exactness of the proposed algorithm is not established. Theorems 3, 5 and 6, which depend on Theorem 2, are likewise unproven