|
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$.
Bibtex entry:
| AUTHOR | = | {T{\'o}thm{\'e}r{\'e}sz, Lilla}, |
| TITLE | = | {Rotor-routing reachability is easy, chip-firing reachability is hard}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2021}, |
| NUMBER | = | {TR-2021-01} |