TR-2015-10

On the complexity of the chip-firing reachability problem

Bálint Hujter, Viktor Kiss, Lilla Tóthmérész

Published in:
Proc. Amer. Math. Soc. 145 (2017), 3343-3356. DOI link



Abstract

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.


Older versions:

Bibtex entry:

@techreport{egres-15-10,
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 egres.elte.hu}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2015},
NUMBER = {TR-2015-10}
}


Last modification: 21.3.2024. Please email your comments to Tamás Király!