2026-07-20T05:32:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26465 2026-07-01T07:16:11Z ddc:004 open_access

Tight Bounds for Sampling q-Colorings via Coupling from the Past Ding, Tianxing Liu, Hongyang Yin, Yitong Zhou, Can perfect sampling coupling from the past graph coloring bounding chains Markov chains 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tianxing Ding and Hongyang Liu and Yitong Yin and Can Zhou 2026 Is Part Of LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2026.76 urn:nbn:de:0030-drops-264657 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.76 eng https://creativecommons.org/licenses/by/4.0/legalcode