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

Since ARRIVAL is contained in $\mathrm{𝖭𝖯}\cap \mathrm{𝖢𝗈𝖭𝖯}$, it also naturally fits into the complexity class $\mathrm{𝖳𝖥𝖭𝖯}$, which contains total problems with efficiently verifiable solutions. In fact, after a series of results for containment in subclasses of $\mathrm{𝖳𝖥𝖭𝖯}$ [20, 15], we now know that ARRIVAL is contained in $\mathrm{𝖴𝖤𝖮𝖯𝖫}$ [14].

Going into a slightly different direction, Gärtner et al. [15] proved that ARRIVAL is also contained in $\mathrm{𝖴𝖯}$ and $\mathrm{𝖢𝗈𝖴𝖯}$, the analogues of $\mathrm{𝖭𝖯}$ and $\mathrm{𝖢𝗈𝖭𝖯}$ with unique solutions. In fact, it would not be hard to rederive this using our reduction to ${\mathrm{\ell }}_1$-contraction: The idea is that the fixed point acts as an efficient certificate for both YES- and NO-instances and it must be unique due to the contraction property.

It is also known that ARRIVAL can be solved in polynomial time on some restricted graph classes. For example, a result due to Priezzhev et al. [22] implies that ARRIVAL can be solved by simulation in polynomial time on Eulerian graphs. Other results include polynomial-time algorithms on tree-like multigraphs [1] and path-like multigraphs with many tokens [2]. More recently, algorithms running in quasi-polynomial-time were given for the case of tree-like multigraphs with many tokens [17]. Our algorithm effectively generalizes this result to all graphs of bounded treewidth.

Finally, further variants of ARRIVAL have been studied in the past, including a stochastic variant [25], a recursive variant [26], as well as variants with one or two players [13].

As explained above, our results are actually obtained for a generalization of ARRIVAL called G-ARRIVAL. Thus, we will start Section 2 by formally introducing G-ARRIVAL. We also use Section 2 to recall further terminology and notation from the literature that will be useful for our arguments.

Note that instead of formally introducing the notion of treewidth and tree decompositions, we will directly work with so-called balanced separators instead. The reason for this choice of exposition is that our parameterized algorithm actually exploits the existence of small balanced separators (and not tree decompositions themselves), which are guaranteed to exist in graphs of small treewidth (see Section 2.1 for more details).

We describe our parameterized algorithm in Section 3. We start the exposition with our simple recursive algorithm for G-ARRIVAL (Section 3.1), which provides a framework from which we will derive the parameterized algorithm in Section 3.3. In Section 3.2, we additionally explain how the subexponential upper bound due to Gärtner et al. [16] and polynomial-time upper bounds on graphs with a bounded feedback vertex set [16] can be rederived from our framework.

Finally, Section 4 contains our reduction to the problem of finding an approximate fixed point of a ${\mathrm{\ell }}_1$-contraction map. Crucially, given an instance of G-ARRIVAL, we define a function $f:{ℝ}_{\ge 0}^n\to {ℝ}_{\ge 0}^n$ that is contracting and thus has a unique fixed point. We then prove that a reasonably good approximation of this fixed point will give away the solution to the G-ARRIVAL-instance. The function can be restricted to a compact subset of ${ℝ}_{\ge 0}^n$ and scaled to fit into ${[0,1]}^n$, if desired.

Treewidth is a well-established graph parameter that plays an important role in parameterized algorithms, and it is intimately related to the notion of balanced separators (see e.g. [10, Chapter 7]). As is the case with many applications on graphs of bounded treewidth, our algorithm actually exploits the existence of balanced separators and can be formulated without computations of tree decompositions. Hence, we will refrain from formally introducing tree decompositions and instead focus on balanced separators.

Given an undirected graph $G=(V,E)$ and a subset $S\subseteq V$ of its vertices, we use $G-S$ to denote the graph resulting from deleting the vertices in $S$ and their incident edges from $G$. We call $S$ a balanced separator if each connected component in $G-S$ contains at most $\frac{1}{2}|V|$ vertices. Note that this does not necessarily imply that $G-S$ must have more than one connected component and it could even be an empty graph (despite what the term separator may suggest): Concretely, any set $S$ of size at least $\frac{1}{2}|V|$ is a balanced separator, and thus there always exists a balanced separator. Using a brute-force approach, we can find a smallest balanced separator $S$ in $G$ in time ${|V|}^{𝒪(|S|)}$.

The following connection between treewidth and balanced separators is crucial for us.

This lemma allows us to use the treewidth of $G$ to infer the existence of small balanced separators in all induced subgraphs of $G$.

All of the previous concepts are defined on undirected graphs. Since we will be working exclusively with directed graphs, we will adopt the following convention: When used on a directed graph, the terms treewidth and balanced separators are to be interpreted with respect to the underlying simple undirected graph.

We will be interested in the Manhattan distance, which is induced by the ${\mathrm{\ell }}_1$-norm. Concretely, we use $\parallel x\parallel :={\sum }_{i=1}^n|x_i|$ to denote the ${\mathrm{\ell }}_1$-norm of a vector $x\in {ℝ}^n$. The Manhattan distance of $x,y\in {ℝ}^n$ is then given by $\parallel x-y\parallel$.

We are mainly concerned with the non-negative orthant ${ℝ}_{\ge 0}^n\subseteq {ℝ}^n$. A function $f:{ℝ}_{\ge 0}^n\to {ℝ}_{\ge 0}^n$ is called a $\lambda$-contraction (or is $\lambda$-contracting) for some $\lambda \in [0,1)$ if and only if $\parallel f(x)-f(y)\parallel \le \lambda \parallel x-y\parallel$ for all $x,y\in {ℝ}_{\ge 0}^n$. Banach’s fixed point theorem [4] implies that such a contracting function admits a unique fixed point. If $f$ only satisfies the weaker property $\parallel f(x)-f(y)\parallel \le \parallel x-y\parallel$ for all $x,y\in {ℝ}_{\ge 0}^n$, we call it non-expansive instead.

In Section 4, we reduce G-ARRIVAL to the following computational problem: Given access to a $\lambda$-contraction $f:{ℝ}_{\ge 0}^n\to {ℝ}_{\ge 0}^n$, find an $\epsilon$-approximate fixed point of $f$, i.e. a point $x\in {ℝ}_{\ge 0}^n$ such that $\parallel f(x)-x\parallel \le \epsilon$. We will also point out how the domain of our function $f$ can be restricted to ${[0,1]}^n$, if desired.

Another property that we need in some of our proofs is monotonicity with respect to the coordinate-wise partial order. Concretely, we call a function $f:X\subseteq {ℝ}_{\ge 0}^n\to {ℝ}_{\ge 0}^n$ monotone if and only if $x\le y$ implies $f(x)\le f(y)$ for all $x,y\in X$, where $\le$ denotes coordinate-wise comparison.

We start by explaining a simple recursive algorithm for G-ARRIVAL that is inspired by the approach of Gärtner et al. [16]: The algorithm chooses an arbitrary non-terminal $p\in V\setminus T$ that we call the pivot, and makes a guess $a\in {\mathbb{N}}_0$ for the outflow of $p$ in an integral switching flow. In order to verify the guess, $p$ is converted to a terminal and $t_p^{+}≔a$ tokens are assigned to start at $p$. In this way, we obtain again an instance of G-ARRIVAL with one more terminal. After solving this subinstance, we can check our guess by looking at the number of tokens $t_p^{-}$ that arrive at $p$ in the subinstance. If we find that $t_p^{-}=a=t_p^{+}$, the integral switching flow obtained for the subinstance is also an integral switching flow for the original instance where $p$ is not a terminal. Otherwise, we have or $t_p^{-}>a$ and we use this information to adjust our guess in a binary search fashion. We make this precise in Algorithm 1 and use the remainder of this section to prove that Algorithm 1 is correct.

Picking the pivot $p\in V\setminus T$ in Algorithm 1 arbitrarily seems quite naive. In this section, we explain how applying the ideas of Gärtner et al. [16] yields a subexponential upper bound.

Given those two observations, it is now not hard to adapt Algorithm 1 to run in subexponential-time: We first precompute the set $S$ from Lemma 7 in linear time. Then, we run Algorithm 1 with two changes: In the recursive step, we make sure to always pick a pivot $p$ from $S$ instead of all of $V\setminus T$. Further, we add a new base case that applies the algorithm from Lemma 6 as soon as the parameter $\mathrm{\ell }$ from Lemma 6 has shrunk to $𝒪(\sqrt{|V|}\log |V|)$, which is guaranteed to happen at the latest once all of the vertices in $S$ have been turned into terminals. With these two changes, the recursion depth will become $𝒪(\sqrt{|V|})$, and since the base case also runs in time exponential only in $𝒪(\sqrt{|V|}\log |V|)$, we get an overall subexponential runtime.

As observed by Gärtner et al. [16], one can do better on graphs with a small feedback vertex set: The crucial ingredient is that G-ARRIVAL can be solved efficiently on acyclic graphs by greedy simulation of the tokens. Using this as a base case and choosing pivots from a feedback vertex set yields yet another instantiation of the framework provided by the recursive algorithm. Concretely, this yields a polynomial-time algorithm on graphs with a bounded feedback vertex set.

We now describe an adaptation of Algorithm 1 that works well on graphs of small treewidth. The general idea is again to pick the pivot $p\in V\setminus T$ appropriately. Concretely, as mentioned in Section 2.1, small treewidth ensures small balanced separators in all induced subgraphs of our input graph. Thus, it seems intuitive that in each step, we should pick the pivot $p$ from a balanced separator of the graph induced by the remaining non-terminals. Eventually, this should disconnect the induced graph into independent subinstances, each with a significantly smaller number of non-terminals. Recursing on all subinstances independently yields the desired speedup. We make this precise in Algorithm 2 and analyse the algorithm in the remainder of this section.

Consider a vector $x\in {ℝ}_{\ge 0}^n$ and think of it as token mass that is distributed among the vertices of a switch graph, with $x_v$ token mass currently occupying vertex $v$. We want to define a notion of moving all (possibly fractional) tokens by one step each while respecting the switching rules. The following one-step update function captures this idea, with the intuition that $f{(x)}_v$ is the amount token mass that $v\in V$ receives from its predecessors.

As we have seen, the one-step update function and its projection are non-expansive with respect to the Manhattan distance. In this section, we make them contracting by artificially introducing a contraction factor.