Complexity of the halting problem for simple 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. A simple digraph here has no loops and at most one arc for each ordered pair of distinct vertices; opposite arcs are allowed. The halting decision problem asks whether its given chip distribution is terminating.

Statement recorded in the supplied source.

Is the chip-firing halting decision problem NP-complete for simple digraphs? [S2]

Short English statement

Is deciding chip-firing termination NP-complete even when there are no parallel arcs?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3000018 (AMR-029-0018). 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.