Complexity of the halting problem for Eulerian multigraphs
From Egres Open
Is the chip-firing halting problem in P for Eulerian digraphs with multiple edges?
- The chip-firing halting problem is in NP [math] \cap [/math] co-NP for Eulerian digraphs with multiple edges .
- The chip-firing halting problem for simple Eulerian digraphs is in P 
- The chip-firing halting problem for general digraphs (with multiple edges) is NP-complete .
- By the duality between chip-firing games and graph divisor theory, a positive answer for Complexity of computing a v-reduced divisor in multigraphs would imply a positive answer for this problem.