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.
Additional Information
- Bálint Hujter
- Affiliation: MTA-ELTE Egerváry Research Group, Department of Operations Research, Eötvös Loránd University, Budapest, Hungary
- Email: hujterb@cs.elte.hu
- Viktor Kiss
- Affiliation: Department of Analysis, Eötvös Loránd University, Budapest, Hungary
- MR Author ID: 1105923
- Email: kivi@cs.elte.hu
- Lilla Tóthmérész
- Affiliation: MTA-ELTE Egerváry Research Group, Department of Computer Science, Eötvös Loránd University, Budapest, Hungary
- MR Author ID: 1039613
- Email: tmlilla@cs.elte.hu
- Received by editor(s): December 2, 2015
- Received by editor(s) in revised form: September 21, 2016
- Published electronically: February 15, 2017
- Additional Notes: The first author was supported by the Hungarian Scientific Research Fund - OTKA K109240.
The second author was supported by the Hungarian Scientific Research Fund - OTKA 104178, 113047.
The third author was supported by the Hungarian Scientific Research Fund - OTKA K109240. - Communicated by: Patricia L. Hersh
- © Copyright 2017 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 145 (2017), 3343-3356
- MSC (2010): Primary 05C57, 05C50, 68Q25
- DOI: https://doi.org/10.1090/proc/13498
- MathSciNet review: 3652788