Complexity of the chip-firing reachability problem for general digraphs

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=(V,A)$ be a finite loopless directed multigraph, with $a_{uv}$ arcs from $u$ to $v$ and $d^+(v)=\sum_w a_{vw}$. A chip distribution is $x\in\mathbb Z_{\ge0}^{V}$. Firing $v$ is legal when $x(v)\ge d^+(v)$ and changes $x$ by removing $d^+(v)$ chips at $v$ and sending one chip along each outgoing arc. Reachability permits any finite legal firing sequence, including the empty sequence. A distribution is terminating if no infinite legal firing sequence starts from it; equivalently a maximal legal game reaches a distribution with no legal firing. The original legal-firing convention includes a zero-outdegree vertex, whose firing has no effect. Arc multiplicities and chip counts are binary encoded. Write $x\rightsquigarrow y$ for legal reachability between two specified distributions. The decision problem has input $(G,x,y)$ and asks whether $x\rightsquigarrow y$.

Statement recorded in the supplied source.

Is this chip-firing reachability decision problem coNP-hard under polynomial-time reductions for general digraphs? [S2]

Short English statement

Is legal chip-firing reachability on general directed graphs coNP-hard?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000016 (AMR-029-0016). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 B. Hujter, V. Kiss and L. Tóthmérész, On the complexity of the chip-firing reachability problem (2017), Sections 1 and 2.1--2.4; Section 5, Problems 19 and 22, pp.12--13. https://arxiv.org/pdf/1507.03209.