On the complexity of the chip-firing reachability problem

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

doi:10.1090/proc/13498

On the complexity of the chip-firing reachability problem
HTML articles powered by AMS MathViewer

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

Proc. Amer. Math. Soc. 145 (2017), 3343-3356 Request permission

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.

References

L. Babai and E. Toumpakari, A structure theory of the sandpile monoid for directed graphs, 2010.
Matthew Baker and Serguei Norine, Riemann-Roch and Abel-Jacobi theory on a finite graph, Adv. Math. 215 (2007), no. 2, 766–788. MR 2355607, DOI 10.1016/j.aim.2007.04.012
Anders Björner and László Lovász, Chip-firing games on directed graphs, J. Algebraic Combin. 1 (1992), no. 4, 305–328. MR 1203679, DOI 10.1023/A:1022467132614
Anders Björner, László Lovász, and Peter W. Shor, Chip-firing games on graphs, European J. Combin. 12 (1991), no. 4, 283–291. MR 1120415, DOI 10.1016/S0195-6698(13)80111-4
Benjamin Bond and Lionel Levine, Abelian networks I. Foundations and examples, SIAM J. Discrete Math. 30 (2016), no. 2, 856–874. MR 3493110, DOI 10.1137/15M1030984
Matthew Farrell and Lionel Levine, CoEulerian graphs, Proc. Amer. Math. Soc. 144 (2016), no. 7, 2847–2860. MR 3487219, DOI 10.1090/proc/12952
Martin Grötschel, László Lovász, and Alexander Schrijver, Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics: Study and Research Texts, vol. 2, Springer-Verlag, Berlin, 1988. MR 936633, DOI 10.1007/978-3-642-97881-4
Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson, Chip-firing and rotor-routing on directed graphs, In and out of equilibrium. 2, Progr. Probab., vol. 60, Birkhäuser, Basel, 2008, pp. 331–364. MR 2477390, DOI 10.1007/978-3-7643-8786-0_{1}7
J. van Dobben de Bruyn and D. Gijswijt, Treewidth is a lower bound on graph gonality, Preprint, arXiv:1407.7055, 2014.
J. van Dobben de Bruyn, Reduced divisors and gonality in finite graphs, Bachelor’s thesis, Mathematisch Instituut, Universiteit Leiden, 2012.
Á. Weisz, A koronglövő játék (in Hungarian), Bachelor’s thesis, Institute of Mathematics, Eötvös University, 2014.