Arriving at faster solutions for token paths in switch digraphs
ARRIVAL in cube-root subexponential time
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The ARRIVAL problem asks where a token traveling through a network with switches ends up first. The authors improve on previous methods by guessing paths in groups, rather than all at once or one by one, speeding up the search significantly. They use a mathematical approach involving special points called centerpoints to narrow down where the token could end up. Their method breaks down a complex problem into smaller parts and solves it faster than before.
What this means in practice
- •For algorithm designers: Use improved fixed point search techniques to develop faster algorithms for probabilistic and combinatorial path problems.
- •For complexity theorists: Employ this subexponential time result to better understand the complexity boundary of problems in NP intersect coNP.
A theory result. No direct application yet.
Authors
Ebrahim Ghorbani, Raul Lopes, Matthias Mnich
Abstract
In the ARRIVAL problem, a token travels through a switch digraph: at every vertex, it leaves along one of two out-arcs, and the two are used alternately. The question is which of two terminals the token reaches first. ARRIVAL lies in $\mathsf{NP} \cap \mathsf{coNP}$, but no polynomial-time algorithm is known.The fastest known algorithms turn some vertices into terminals and search for consistent guesses of the numbers of tokens that these vertices send out. The first, due to Gärtner et al. [ICALP 2021], searches all vertices at once with an algorithm for fixed points of monotone maps, and the second, due to Haslebacher [ICALP 2025], searches one vertex at a time by binary search. Both search for a fixed point of the same map, which returns how many tokens arrive at the guessed vertices. We guess the vertices in blocks of $k$, between these two extremes, which needs a search in $k$ dimensions with few evaluations of this map. To do so, we build on the connection between ARRIVAL and $\ell_1$-contractions established in the second of these works. We search with $\ell_1$-centerpoints of the remaining guesses, which are guaranteed to exist by Haslebacher et al. [FOCS 2025], and which we approximate deterministically. In order to prove our results, we show how to find the least fixed points of maps from $\{0, \ldots, N\}^k$ to itself that have unit increments. For ARRIVAL on $n$-vertex switch digraphs, this gives run time $2^{\mathcal{O}(n^{1/3} \cdot \log^{2/3} n)}$, improving the previous time bound of $n^{\mathcal{O}(\sqrt{n})}$. We work with the more general \garrival problem, with many tokens and several terminals, and solve it in the same time when there are at most $2^n$ tokens.