Rotor-routing reachability is easy, chip-firing reachability is hard
| Autor: | Lilla Tóthmérész |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
Polynomial hierarchy
Polynomial Reachability problem Eulerian path Decidability Combinatorics symbols.namesake Reachability Computer Science::Logic in Computer Science FOS: Mathematics symbols Mathematics - Combinatorics 68Q17 05C50 05C85 Discrete Mathematics and Combinatorics Combinatorics (math.CO) Adjacency matrix Time complexity Computer Science::Formal Languages and Automata Theory Mathematics |
| Zdroj: | European Journal of Combinatorics. 101:103466 |
| ISSN: | 0195-6698 |
| DOI: | 10.1016/j.ejc.2021.103466 |
| Popis: | 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. We encode graphs by their adjacency matrix, and we encode ribbon structures “succinctly”, only remembering the number of consecutive parallel edges. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect