Complexity of computing the rotor-router action

Let [math]G[/math] be an undirected graph. What is the complexity of computing the rotor-router action of the sandpile group of [math]G[/math] on the spanning trees of [math]G[/math]?

Remarks

• The rotor-router action has been defined by Holroyd et al. .

• This problem is a special case of computing the halting configuration of the rotor-routing game. More precisely, we need to be able to solve the following problem: Let [math]D[/math] be the directed graph where we substitute each (undirected) edge of [math]G[/math] by two oppositely directed edges, then we delete the out-edges of a fixed root vertex [math]q[/math]. Suppose that a chip-and-rotor configuration is given on [math]D[/math] where the number of chips is nonnegative outside [math]q[/math]. What is the halting configuration of the rotor-routing game on this input?

• It can be checked in polynomial time whether a given sandpile group element [math]x[/math] sends a given spanning tree [math]T[/math] to another given spanning tree [math]T'[/math].