Options
A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs
Citation Link: https://doi.org/10.15480/882.14836
Publikationstyp
Conference Paper
Date Issued
2025-02-24
Sprache
English
TORE-DOI
First published in
Number in series
327
Article Number
39
Citation
International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl, Leibniz-Zentrum für Informatik
Propp machines, or rotor-router models, are a classic tool to simulate random systems in forms of Markov chains by deterministic systems. To this end, the nodes of the Markov chain are replaced by switching nodes, which maintain a queue over their outgoing arcs, and a particle sent through the system traverses the top arc of the queue which is then moved to the end of the queue and the particle arrives at the next node. A key question to answer about such systems is whether a single particle can reach a particular target node, given as input an initial configuration of the queues at all switching nodes. This question was introduced by Dohrau et al. (2017) under the name of Arrival.
A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in NP ∩co-NP; yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021).
We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time.
Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs.
A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in NP ∩co-NP; yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021).
We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time.
Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs.
DDC Class
004: Computer Sciences
005.1: Programming
519: Applied Mathematics, Probabilities
Publication version
publishedVersion
Loading...
Name
LIPIcs.STACS.2025.39.pdf
Size
853.78 KB
Format
Adobe PDF