Rotor-routing reachability is easy, chip-firing reachability is hard

Combinatorics Seminar
Friday, March 5, 2021 - 3:00pm for 1 hour (actually 50 minutes)
Location (To receive the password, please email Lutz Warnke
Lilla Tóthmérész – Eötvös Loránd University
Lutz Warnke

Chip-firing and rotor-routing are two well-studied examples of Abelian networks. We study the complexity of their respective reachability problems. We show that the rotor-routing reachability problem is decidable in polynomial time, and we give a simple characterization of when a chip-and-rotor configuration is reachable from another one. For chip-firing, it has been known that the reachability problem is in P if we have a class of graphs whose period length is polynomial (for example, Eulerian digraphs). Here we show that in the general case, chip-firing reachability is hard in the sense that if the chip-firing reachability problem were in P for general digraphs, then the polynomial hierarchy would collapse to NP.

Talk based on