An FPRAS for counting list packings
An FPRAS for counting list packings
Let be a maximum-degree bound, let , and consider graphs of maximum degree at most . A -list packing assigns colors from each vertex's list so that adjacent vertices receive disjoint color sets. Counting conjecture. For each and , there is a fully polynomial randomized approximation scheme (FPRAS) for counting the number of -list packings of graphs of maximum degree . This would give an efficient approximate-counting algorithm throughout the stated range, extending the algorithmic study of list packing; the source does not indicate that the conjecture has been resolved.
Sources & referencesView supporting material
Primary source
Evan Camrud, Ewan Davies, Alex Karduna and Holden Lee, “Sampling List Packings”, arXiv:2402.03520 (2024).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.