# 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?

## Remarks

- The chip-firing halting problem is in
**NP**[math] \cap [/math]**co-NP**for Eulerian digraphs with multiple edges^{[1]}. - The chip-firing halting problem for simple Eulerian digraphs is in
**P**^{[2]} - The chip-firing halting problem for general digraphs (with multiple edges) is
**NP**-complete^{[3]}. - 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.

## References

- ↑ B. Hujter, V. Kiss, L. Tóthmérész,
*On the complexity of the*chip-firing reachability problem*, EGRES Technical Report* - ↑ A. Björner, L. Lovász
*, Chip-firing games on directed graphs*, DOI link, Author link - ↑ M. Farrell, L. Levine,
*Coeulerian graphs*, DOI link, ArXiv link