ON THE COMPLEXITY OF THE CHIP-FIRING REACHABILITY PROBLEM

Hujter, Bálint and Kiss, Viktor and Tóthmérész, Lilla (2017) ON THE COMPLEXITY OF THE CHIP-FIRING REACHABILITY PROBLEM. PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 145 (8). pp. 3343-3356. ISSN 0002-9939

Preview

Text 1507.03209v4.pdf Download (207kB) | Preview

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 strongly 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. 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.

Actions (login required)

Edit Item