Record link: 
http://hdl.handle.net/20.500.12708/230323
-
Title: 
Sinks and Ladders: ARRIVAL and SSG with Two Vertices per Level
en
Citation: 
Gärtner, B., Haslebacher, S., & Hoang, H. P. (2026). Sinks and Ladders: ARRIVAL and SSG with Two Vertices per Level. In J. Iacono (Ed.), 13th International Conference on Fun with Algorithms (FUN 2026). Schloss Dagstuhl. https://doi.org/10.4230/LIPIcs.FUN.2026.19
-
Publisher DOI: 
10.4230/LIPIcs.FUN.2026.19
-
Publication Type: 
Inproceedings - Full-Paper Contribution
en
Language: 
English
-
Authors: 
Gärtner, Bernd 
Haslebacher, Sebastian 
Hoang, Hung P. 
-
Organisational Unit: 
E192-01 - Forschungsbereich Algorithms and Complexity 
-
Published in: 
13th International Conference on Fun with Algorithms (FUN 2026) 
-
ISBN: 
978-3-95977-417-8
-
Volume: 
366
-
Date (published): 
15-May-2026
-
Event name: 
13th International Conference on Fun with Algorithms (FUN 2026) 
en
Event date: 
18-May-2026 - 22-May-2026
-
Event place: 
Porquerolles, France
-
Number of Pages: 
16
-
Publisher: 
Schloss Dagstuhl, Leibniz
-
Keywords: 
ARRIVAL; Rotor-Routing; Simple Stochastic Games
en
Abstract: 
ARRIVAL is the problem of deciding whether a token, following a deterministic process, eventually reaches a designated destination. While the problem is known to lie in NP∩CoNP, whether it can be solved in polynomial time remains a major open question. In this article, we study ladders, a class of graphs that constitutes a family of worst-case instances for many existing algorithms, including the currently best known algorithm by Gärtner, Haslebacher, and Hoang (ICALP 2021). We show that ARRIVAL restricted to ladders can be solved in polynomial time, and we further extend this result to stopping binary simple stochastic games (SSG).
en
Research Areas: 
Logic and Computation: 100%
-
Science Branch: 
1020 - Informatik: 80%
1010 - Mathematik: 20%
-
Appears in Collections:
Conference Paper

Show full item record

Page view(s)

9
checked on Aug 26, 2026

Google ScholarTM

Check