An FPRAS for counting list packings

Let Δ\Delta be a maximum-degree bound, let q2Δq\ge 2\Delta, and consider graphs of maximum degree at most Δ\Delta. A qq-list packing assigns colors from each vertex's list so that adjacent vertices receive disjoint color sets. Counting conjecture. For each Δ\Delta and q2Δq\ge 2\Delta, there is a fully polynomial randomized approximation scheme (FPRAS) for counting the number of qq-list packings of graphs of maximum degree Δ\Delta. 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.