DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.76

Tight Bounds for Sampling q-Colorings via Coupling from the Past

Authors: Tianxing Ding, Hongyang Liu, Yitong Yin, and Can Zhou

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

The Coupling from the Past (CFTP) paradigm is a canonical method for perfect sampling. For uniform sampling of proper q-colorings in graphs with maximum degree Δ, the bounding chains of [Huber, STOC '98] provide a systematic framework for efficiently implementing CFTP algorithms within the classical regime q ≥ (1+o(1))Δ². This was subsequently improved to q > 3Δ by [Bhandari and Chakraborty, STOC '20] and to q ≥ (8/3 + o(1))Δ by [Jain, Sah, and Sawhney, STOC '21]. In this work, we establish the asymptotically tight threshold for bounding-chain-based CFTP algorithms for graph colorings. We prove a lower bound showing that all such algorithms satisfying the standard contraction property require q ≥ 2.5Δ, and we present an efficient CFTP algorithm that achieves this asymptotically optimal threshold q ≥ (2.5 + o(1))Δ via an optimal design of bounding chains.

Cite as

Tianxing Ding, Hongyang Liu, Yitong Yin, and Can Zhou. Tight Bounds for Sampling q-Colorings via Coupling from the Past. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 76:1-76:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ding_et_al:LIPIcs.ICALP.2026.76,
  author =	{Ding, Tianxing and Liu, Hongyang and Yin, Yitong and Zhou, Can},
  title =	{{Tight Bounds for Sampling q-Colorings via Coupling from the Past}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{76:1--76:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.76},
  URN =		{urn:nbn:de:0030-drops-264657},
  doi =		{10.4230/LIPIcs.ICALP.2026.76},
  annote =	{Keywords: perfect sampling, coupling from the past, graph coloring, bounding chains, Markov chains}
}

Search Results

Documents authored by Zhou, Can

Tight Bounds for Sampling q-Colorings via Coupling from the Past

Abstract

Cite as

Thanks for your feedback!

Could not send message