Linear Extensions of Rotor-Routing in Directed Graphs: Reachability Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909916135948288 |
|---|---|
| author | Auger, David Coucheney, Pierre Etse, Kossi Roland |
| author_facet | Auger, David Coucheney, Pierre Etse, Kossi Roland |
| contents | We develop a unified framework for rotor-routing that extends the classical model to a broad class of multigraphs equipped with Generalized Rotor Mechanisms (GRM). This perspective places rotor-routing on the same footing as abelian sandpiles by interpreting both as conservative instances of Vector Addition Systems (VAS). Within this framework, routing becomes a linear transformation governed by arc mechanisms, while legality is enforced through non-negativity constraints.
We introduce four routing models -- free routing, standard rotor-routing, cyclic GRM routing, and fully general GRM routing -- and study their reachability problems in both the linear and legal settings. Our results generalize previous characterizations for standard rotor-routing and extend them to the GRM setting. In particular, we show that legal reachability in GRM multigraphs is NP-complete, whereas the cyclic GRM routing model, which includes the classical rotor-router, admits a polynomial-time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_18364 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Linear Extensions of Rotor-Routing in Directed Graphs: Reachability Problems Auger, David Coucheney, Pierre Etse, Kossi Roland Discrete Mathematics Combinatorics We develop a unified framework for rotor-routing that extends the classical model to a broad class of multigraphs equipped with Generalized Rotor Mechanisms (GRM). This perspective places rotor-routing on the same footing as abelian sandpiles by interpreting both as conservative instances of Vector Addition Systems (VAS). Within this framework, routing becomes a linear transformation governed by arc mechanisms, while legality is enforced through non-negativity constraints. We introduce four routing models -- free routing, standard rotor-routing, cyclic GRM routing, and fully general GRM routing -- and study their reachability problems in both the linear and legal settings. Our results generalize previous characterizations for standard rotor-routing and extend them to the GRM setting. In particular, we show that legal reachability in GRM multigraphs is NP-complete, whereas the cyclic GRM routing model, which includes the classical rotor-router, admits a polynomial-time algorithm. |
| title | Linear Extensions of Rotor-Routing in Directed Graphs: Reachability Problems |
| topic | Discrete Mathematics Combinatorics |
| url | https://arxiv.org/abs/2411.18364 |