DROPS

Document

DOI: 10.4230/LIPIcs.ITCS.2025.24

Sampling List Packings

Authors: Evan Camrud, Ewan Davies, Alex Karduna, and Holden Lee

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract

We initiate the study of approximately counting the number of list packings of a graph. The analogous problem for usual vertex coloring and list coloring has attracted substantial attention. For list packing the setup is similar, but we seek a full decomposition of the lists of colors into pairwise-disjoint proper list colorings. The existence of a list packing implies the existence of a list coloring, but the converse is false. Recent works on list packing have focused on existence or extremal results of on the number of list packings, but here we turn to the algorithmic aspects of counting and sampling. In graphs of maximum degree Δ and when the number of colors is at least Ω(Δ²), we give a fully polynomial-time randomized approximation scheme (FPRAS) based on rapid mixing of a natural Markov chain (the Glauber dynamics) which we analyze with the path coupling technique. Some motivation for our work is the investigation of an atypical spin system, one where the number of spins for each vertex is much larger than the graph degree.

Cite as

Evan Camrud, Ewan Davies, Alex Karduna, and Holden Lee. Sampling List Packings. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 24:1-24:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{camrud_et_al:LIPIcs.ITCS.2025.24,
  author =	{Camrud, Evan and Davies, Ewan and Karduna, Alex and Lee, Holden},
  title =	{{Sampling List Packings}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{24:1--24:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.24},
  URN =		{urn:nbn:de:0030-drops-226528},
  doi =		{10.4230/LIPIcs.ITCS.2025.24},
  annote =	{Keywords: List packing, Graph colouring, Markov chains, Path coupling}
}

Search Results

Documents authored by Camrud, Evan

Sampling List Packings

Abstract

Cite as

Thanks for your feedback!

Could not send message