2026-07-23T12:54:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25738 2026-06-23T12:45:30Z ddc:004 open_access

Sinks and Ladders: ARRIVAL and SSG with Two Vertices per Level Gärtner, Bernd Haslebacher, Sebastian Hoang, Hung P. ARRIVAL Rotor-Routing Simple Stochastic Games 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Bernd Gärtner and Sebastian Haslebacher and Hung P. Hoang 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.19 urn:nbn:de:0030-drops-257385 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.19 eng https://creativecommons.org/licenses/by/4.0/legalcode