ARRIVAL: Recursive Framework & ℓ$_1$-Contraction

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 ∩ 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(√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 ℓ$_1$-contracting function f : [0, 1]$^n$ → [0, 1]$^n$. Finding such fixed points is a well-studied problem in the case of the ℓ$_2$-metric and the ℓ$_∞$-metric, but little is known about the ℓ$_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 ℓ$_∞$-contraction.