Sinks and Ladders: ARRIVAL and SSG with Two Vertices per Level

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).