ARRIVAL: Recursive Framework & $\ell_1$-Contraction
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912461465059328 |
|---|---|
| author | Haslebacher, Sebastian |
| author_facet | Haslebacher, Sebastian |
| contents | 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 \rightarrow [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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_06477 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | ARRIVAL: Recursive Framework & $\ell_1$-Contraction Haslebacher, Sebastian Data Structures and Algorithms 05C57, 05C85, 68Q25, 68W05, 91A46 F.2.2; G.2.2 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 \rightarrow [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. |
| title | ARRIVAL: Recursive Framework & $\ell_1$-Contraction |
| topic | Data Structures and Algorithms 05C57, 05C85, 68Q25, 68W05, 91A46 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2502.06477 |