Complexity of the halting problem for simple digraphs
From Egres Open
Is it true that the chip-firing halting problem for simple digraphs is NP-complete?
Remarks
The question is posed in [1].
It is proved in [1] that the halting problem for digraphs with multiple edges is NP-complete.
References
- ↑ 1.0 1.1 M. Farrell, L. Levine, Coeulerian graphs, DOI link, ArXiv link
