Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866910103370727424 |
|---|---|
| author | Moka, Sarat Vahedi, Ava |
| author_facet | Moka, Sarat Vahedi, Ava |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_03947 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling Moka, Sarat Vahedi, Ava Data Structures and Algorithms Computational Complexity Probability 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. |
| title | Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling |
| topic | Data Structures and Algorithms Computational Complexity Probability |
| url | https://arxiv.org/abs/2604.03947 |