|
In this paper, we study the complexity of the chip-firing reachability problem.
We show that for Eulerian digraphs, the reachability problem can be decided in
polynomial time, even if the digraph has multiple edges. We also show a special
case when the reachability problem can be decided in polynomial time for
general digraphs: if the target distribution is recurrent restricted to each
strongly connected component. Both of these algorithms are strongly polynomial.
As a further positive result, we show that the chip-firing reachability problem
is in co-NP for general digraphs. We also show that the chip-firing halting
problem is in co-NP for Eulerian digraphs.
An earlier version (under the title "Reachability of recurrent positions in the chip-firing game") is available here.
Bibtex entry:
| AUTHOR | = | {Hujter, B{\'a}lint and Kiss, Viktor and T{\'o}thm{\'e}r{\'e}sz, Lilla}, |
| TITLE | = | {On the complexity of the chip-firing reachability problem}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2015}, |
| NUMBER | = | {TR-2015-10} |