ARRIVAL: Recursive Framework & ${\ell }_1$-Contraction

Abstract

ARRIVAL is the problem of deciding which out of two possible destinations will be reached first by a token that moves deterministically along the edges of a directed graph, according to so-called switching rules. It is known to lie in NP $\cap$ CoNP, but not known to lie in P. The state-of-the-art algorithm due to Gärtner et al. (ICALP `21) runs in time $2^{O(\sqrt{n}\log n)}$ on an $n$-vertex graph. We prove that ARRIVAL can be solved in time $2^{O(k{\log }^{2}n)}$ on $n$-vertex graphs of treewidth $k$. Our algorithm is derived by adapting a simple recursive algorithm for a generalization of ARRIVAL called G-ARRIVAL. This simple recursive algorithm acts as a framework from which we can also rederive the subexponential upper bound of Gärtner et al. Our second result is a reduction from G-ARRIVAL to the problem of finding an approximate fixed point of an ${\ell }_1$-contracting function $f:[0,1{]}^n\to [0,1{]}^n$. Finding such fixed points is a well-studied problem in the case of the ${\ell }_2$-metric and the ${\ell }_{\infty }$-metric, but little is known about the ${\ell }_1$-case. Both of our results highlight parallels between ARRIVAL and the Simple Stochastic Games (SSG) problem. Concretely, Chatterjee et al. (SODA `23) gave an algorithm for SSG parameterized by treewidth that achieves a similar bound as we do for ARRIVAL, and SSG is known to reduce to ${\ell }_{\infty }$-contraction.

18 pages