Exact block-product sampling of maximal G-parking functions

Definitions and mathematical statement

Let $G=(V,E)$ be a finite connected loopless undirected graph, with a distinguished sink vertex $q$. Parallel edges may be present and are counted with multiplicity. For a nonempty subset $S\subseteq V\setminus\{q\}$, let $\operatorname{out}_S(v)$ be the number of edges joining $v\in S$ to $V\setminus S$. A $G$-parking function rooted at $q$ is a function $f:V\setminus\{q\}\to\mathbb Z_{\ge0}$ such that \[ \text{for every nonempty }S\subseteq V\setminus\{q\},\quad \text{some }v\in S\text{ satisfies }f(v)<\operatorname{out}_S(v). \] It is maximal if there is no different parking function $g$ with $g(v)\ge f(v)$ for every nonsink vertex. This is maximality in the coordinatewise partial order. Denote the finite set of maximal parking functions by $\mathcal M(G,q)$.

The problem asks for an efficient uniform sampling algorithm for $\mathcal M(G,q)$. More precisely, given the graph and its sink, can a randomized algorithm output each member with probability exactly $1/|\mathcal M(G,q)|$, with expected running time polynomial in the size of an explicit vertex-and-edge description of $G$? Repeated edges are listed individually in this input convention. The output consists of all nonsink coordinate values. Sampling uniformly among all parking functions, or producing a biased distribution on the maximal ones, does not give the requested distribution. For the one-vertex graph the unique empty function supplies the harmless boundary case.

Short English statement

Can maximal graph parking functions be sampled exactly uniformly in expected polynomial time?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 20000970 (AIM-COMBINATORICS-0095), AIM Workshop Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 American Institute of Mathematics, Generalizations of chip-firing and the critical group, item 5. Original workshop question underlying AIM-COMBINATORICS-0095. https://aimath.org/pastworkshops/chipfiringproblems.pdf.