A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs

DOI10.4230/LIPICS.STACS.2025.39MaRDI QIDQ7287776zbMATH OpenFDO

Authors E. Ghorbani, Jonah Leander Hoff, Matthias Mnich

Publication date 24 June 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.STACS.2025.39

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A subexponential algorithm for ARRIVAL
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• ARRIVAL: next stop in CLS
• Generalized ARRIVAL problem for rotor walks in path multigraphs
• Local-to-global principles for the hitting sequence of a rotor walk
• Polynomial time algorithm for ARRIVAL on tree-like multigraphs
• Reachability switching games
• Rotor-routing reachability is easy, chip-firing reachability is hard

Cited in

(1)

• ARRIVAL: recursive framework \& _1-contraction

This page was built for publication: A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7287776)