A subexponential algorithm for ARRIVAL

DOI10.4230/LIPICS.ICALP.2021.69MaRDI QIDQ7241167zbMATH OpenFDO

Authors B. Gärtner, Sebastian Haslebacher, Hung P. Hoang

Publication date 12 May 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICALP.2021.69

zbMATH Keywords

graph gamespseudorandom walksreachabilityswitching systems

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• A fixed-parameter algorithm for the directed feedback vertex set problem
• A lattice-theoretical fixpoint theorem and its applications
• ARRIVAL: a zero-player graph game in \(\text{NP}\cap \text{coNP}\)
• ARRIVAL: next stop in CLS
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Deterministic random walks on the integers
• Did the train reach its destination: the complexity of finding a witness
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Reachability Switching Games
• Reducibility among combinatorial problems
• Rotor walks and Markov chains
• The complexity of mean payoff games on graphs
• The complexity of stochastic games
• Unique end of potential line

Cited in

(2)

• A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs
• ARRIVAL: recursive framework \& _1-contraction

This page was built for publication: A subexponential algorithm for ARRIVAL

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