2026-07-27T17:10:49Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:23472 2025-10-02T12:56:09Z ddc:004 open_access
ARRIVAL: Recursive Framework & 𝓁₁-Contraction Haslebacher, Sebastian ARRIVAL G-ARRIVAL Deterministic Random Walk Rotor-Routing 𝓁₁-Contraction Banach Fixed Point 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 𝖯. The state-of-the-art algorithm due to GΓ€rtner et al. (ICALP `21) runs in time 2^{π’ͺ(√n log n)} on an n-vertex graph. We prove that ARRIVAL can be solved in time 2^{π’ͺ(k logΒ² 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 𝓁₁-contracting function f : [0, 1]ⁿ β†’ [0, 1]ⁿ. Finding such fixed points is a well-studied problem in the case of the 𝓁₂-metric and the 𝓁_∞-metric, but little is known about the 𝓁₁-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. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Sebastian Haslebacher 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.95 urn:nbn:de:0030-drops-234723 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.95 eng https://creativecommons.org/licenses/by/4.0/legalcode