Complexity of computing the rotor-router action

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

Let $G$ be a finite connected undirected loopless multigraph. Supply a cyclic order of incident edges at every vertex (a ribbon structure) and a root $r$. Let $\Delta$ be its integer Laplacian, with diagonal degrees and off-diagonal entries minus edge multiplicities. Its sandpile group is $\operatorname{Pic}^0(G)=\{D\in\mathbb Z^{V(G)}:\sum_v D(v)=0\}/\Delta\mathbb Z^{V(G)}$. Orient a spanning tree $T$ toward $r$, giving one outgoing rotor at each other vertex. The action of $v-r$ on $T$ places one chip at $v$, repeatedly advances its current vertex rotor to the next edge in the cyclic order and moves the chip along that edge, stopping upon first reaching $r$. The resulting rotors form another tree. These commuting bijections and their inverses define the action of every degree-zero divisor, which factors through $\operatorname{Pic}^0(G)$. Encode graph adjacency multiplicities in binary. At each vertex encode the cyclic ribbon order as a cyclic list of runs of consecutive parallel arcs, recording the head of each run and its positive binary-encoded length. A rotor or tree arc is specified by its run and binary position within that run; an ordinary explicit edge list is the special case of runs of length one. The input consists of this graph and ribbon encoding, $r,T$ and a degree-zero divisor representative $D$ with binary-encoded integer coefficients. Complexity is measured in this compressed input length, so it must not assume time polynomial in the expanded number of parallel arcs.

Statement recorded in the supplied source.

Determine the computational complexity of producing the spanning tree $D_r(T)$ obtained by this rotor-router sandpile-group action, for arbitrary such inputs. In particular, is there an algorithm polynomial in the input length rather than in the length of its individual routing simulation? [S2]

Short English statement

Determine how efficiently a specified sandpile-group element can act on a spanning tree by rotor routing.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000015 (AMR-029-0015). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 L. Tóthmérész, Rotor-routing reachability is easy, chip-firing reachability is hard (2022), Section 3, definitions, and final paragraph following Corollary 3.9, pp.8 and15. https://arxiv.org/pdf/2102.11970.
• S3 M. Chan, T. Church and J. A. Grochow, Rotor-routing and spanning trees on planar graphs (2014), Section 2, Definitions and notation, pp.3--4. https://arxiv.org/pdf/1308.2677.