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
