A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs

Ghorbani, Ebrahim; Leander Hoff, Jonah; Mnich, Matthias

doi:10.4230/LIPIcs.STACS.2025.39

A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs

Ebrahim Ghorbani

Hamburg University of Technology, Institute for Algorithms and Complexity, Hamburg, Germany Jonah Leander Hoff Hamburg University of Technology, Institute for Algorithms and Complexity, Hamburg, Germany Matthias Mnich

Hamburg University of Technology, Institute for Algorithms and Complexity, Hamburg, Germany

Abstract

Propp machines, or rotor-router models, are a classic tool to simulate random systems in forms of Markov chains by deterministic systems. To this end, the nodes of the Markov chain are replaced by switching nodes, which maintain a queue over their outgoing arcs, and a particle sent through the system traverses the top arc of the queue which is then moved to the end of the queue and the particle arrives at the next node. A key question to answer about such systems is whether a single particle can reach a particular target node, given as input an initial configuration of the queues at all switching nodes. This question was introduced by Dohrau et al. (2017) under the name of Arrival. A major open question is whether Arrival can be solved in polynomial time, as it is known to lie in $\textsf{NP}\cap\textsf{co-NP}$ ; yet the fastest known algorithm for general instances takes subexponential time (Gärtner et al., ICALP 2021).

We consider a generalized version of Arrival introduced by Auger et al. (RP 2023), which requires routing multiple (potentially exponentially many) particles through a rotor graph. The Multi-Arrival problem is to determine the particle configuration that results from moving all particles from a given initial configuration to sinks. Auger et al. showed that for path-like rotor graphs with a certain uniform rotor order, the problem can be solved in polynomial time.

Our main result is a quasi-polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs for arbitrary rotor orders. Tree-like rotor graphs are directed multigraphs which can be obtained from undirected trees by replacing each edge by an arbitrary number of arcs in either or both directions. For trees of bounded contracted height, such as paths, the algorithm runs in polynomial time and thereby generalizes the result by Auger et al.. Moreover, we give a polynomial-time algorithm for Multi-Arrival on tree-like rotor graphs without parallel arcs.

Keywords and phrases:

Arrival, Rotor-routing, Tree-like Multigraph, Path-Like Multigraph, Fixed-Parameter Tractability

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Randomness, geometry and discrete structures

Funding:

Funded by the project “Hamburg Quantum Computing”, co-financed by ERDF and Fonds of the Hamburg Ministry of Science, Research, Equalities and Districts (BWFGB).

DOI:

10.4230/LIPIcs.STACS.2025.39

Event:

42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Editors:

Olaf Beyersdorff, Michał Pilipczuk, Elaine Pimentel, and Nguyễn Kim Thắng

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

In 2017, Dohrau et al. [3] introduced the Arrival problem, which they intuitively defined as follows:

“Suppose that a train is running along a railway network, starting from a designated origin, with the goal of reaching a designated destination. The network, however, is of a special nature: every time the train traverses a switch, the switch will change its position immediately afterwards. Hence, the next time the train traverses the same switch, the other direction will be taken, so that directions alternate with each traversal of the switch. Given a network with origin and destination, what is the complexity of deciding whether the train, starting at the origin, will eventually reach the destination?”

One may solve Arrival by running the train iteratively according to the outlined rules until reaching a destination. This may require a number of steps which is exponential in the number of switches. Gärtner et al. [6] devised an algorithm for Arrival which runs in subexponential time. It is further known that Arrival lies in $\textsf{NP}\cap\textsf{co-NP}$ [3], which motivated the conjecture that the problem is polynomial-time decidable. As of now, this conjecture is still open, despite some effort [4, 5, 6].

The routing behaviour in Arrival is also known as switching networks, rotor routing, Propp machines, and Eulerian walkers [4, 7, 10]. We adopt the nomenclature of rotor routing and refer to the trains as particles. In rotor routing, particles are routed from each node along its outgoing arcs in a fixed cyclic order called the rotor order. A directed multigraph equipped with a rotor order at each of its nodes is referred to as a rotor graph. Arrival can be seen as determining the unique particle configuration resulting from routing a single particle until it reaches a sink. As the complexity of Arrival in general is unkown, recent efforts focus on identifying families of instances on which Arrival can be solved in polynomial-time. One such family are tree-like rotor graphs, which are rotor graphs whose underlying undirected simple graphs are trees. Note that the class of tree-like rotor graphs is richer than its name may suggest: they can contain arcs in opposite direction, as well as parallel arcs, between the same two nodes. Tree-like rotor graphs are directed multi-graphs that can be obtained from undirected trees by replacing edge undirected edge $\{u,v\}$ by any number $a_{uv}\geq 0$ of arcs $(u,v)$ and any number $a_{vu}\geq 0$ of arcs $(v,u)$ , where $a_{uv}$ and $a_{vu}$ can be different (not both of them should be zero). On tree-like rotor graphs, Arrival was shown to be solvable in polynomial time [1]. More recently, the case of routing multiple (potentially exponentially many) particles on path-like rotor graphs has been studied. Multi-Arrival refers to the problem of determining the particle configuration resulting from a routing that moves all particles from a given initial configuration to the sinks. This resulting configuration has been proved to be unique [2]. Auger et al. [2] showed that for path-like rotor graphs with a certain uniform rotor order, Multi-Arrival can be solved in polynomial-time. Results by Gärtner et al. [6] show that polynomial-time algorithms for Multi-Arrival for a certain family $\cal F$ of rotor graphs yield polynomial-time algorithms for Arrival for rotor graphs that belong to $\cal F$ after deleting constantly many nodes.

Our Contributions.

Our main contributions are algorithms for Multi-Arrival on tree-like rotor graphs. To state them, we introduce the notion of contracted height $\mathsf{ch}(R)$ of a simple rooted tree $R$ as the minimum height over all trees obtained from $R$ by contracting, for each node $v$ of $R$ , one of the arcs to its children. We now state our main results informally, where $\kappa(T)$ is the maximum possible $\mathsf{ch}(\langle T\rangle)$ over all choices of a root, where $\langle T\rangle$ is the simple undirected underlying tree of $T$ .

Theorem 1 (Informal).

Multi-Arrival can be solved on tree-like rotor graph $T$ with $|A(T)|$ arcs in time $\mathcal{O}^{*}\bigl{(}\log^{\kappa(T)+1}|A(T)|\bigr{)}$ , where $\mathcal{O}^{*}$ hides factors polynomial in the input. In particular, Multi-Arrival can be solved in polynomial time if $\kappa(T)=\mathcal{O}\bigl{(}\frac{\log|A(T)|}{\log(\log|A(T)|)}\bigr{)}$ .

We further show that if $\kappa(T)=\mathcal{O}(1)$ (which includes path-like rotor graphs), Multi-Arrival can be solved in time polynomial in $|\hat{A}(T)|$ , where $\hat{A}(T)$ represents the succinct encoding of the arcs, only recording the number of consecutive parallel arcs. Therefore, our results widely generalize the previous algorithms by Auger et al. [2] for path-like rotor graphs with uniform rotor order.

As an important corollary, we deduce that Multi-Arrival on tree-like rotor graphs is fixed-parameter tractable when parameterized by $\kappa(T)$ . That is, Multi-Arrival can be solved in time $f(\kappa(T))\cdot m^{\mathcal{O}(1)}$ on tree-like rotor graphs of size $m$ . Such fixed-parameter algorithms are considered to be advantageous over so-called $\mathsf{XP}$ -algorithms, where the degree of the polynomial depends on the parameter. Indeed, for the related parameter “feedback vertex set size” $\mathsf{fvs}(G)$ , which measures the node deletion distance of the rotor graph $G$ to an acyclic digraph, Gärtner et al. [6] provided an $\mathsf{XP}$ -algorithm with run time $m^{\mathcal{O}(\mathsf{fvs}(G))}$ .

Finally, we show:

Theorem 2 (Informal).

Multi-Arrival is solvable in polynomial time for tree-like rotor graphs without parallel arcs.

2 Preliminaries

2.1 Directed Multigraphs

Throughout, we consider directed multigraphs $G$ with finite node set $V(G)$ and arc set $A(G)$ . An arc with tail $v$ and head $w$ is said to be from $v$ to $w$ . A directed multigraph may have parallel arcs which share the same head-tail pair, and self-loops which are from and to the same node.

For a given node $v\in V(G)$ , we denote by $A^{+}(v)$ the set of arcs whose tail is $v$ and define $d^{+}(v)=|A^{+}(v)|$ . Let $N^{+}(v)$ be the set of out-neighbours of $v$ and let $N^{-}(v)$ be the set of in-neighbours of $v$ . By $d(v,w)$ we denote the number of arcs from $v$ to $w$ . For a directed multigraph $G$ , let $V^{+}(G)$ be the set of nodes with positive out-degree and let $S_{0}(G)$ be the set of the sinks, that is, the nodes with out-degree 0. The underlying undirected simple graph of $G$ is the undirected simple graph $\langle G\rangle$ with node set $V(G)$ which contains an edge $\{v,w\}$ whenever there is an arc between $v$ and $w$ . We call $G$ tree-like (path-like) if $\langle G\rangle$ is a tree (path). A rooted tree is obtained from an undirected tree by designating one node as its root and orienting all edges away from the root.

2.2 Rotor-Routing

Let $G$ be a directed multigraph. For any node $v\in V^{+}(G)$ , a rotor order at $v$ is a cyclic permutation of $A^{+}(v)$ . A rotor order for $G$ is a permutation $\theta$ of $A(G)$ such that, for each $v\in V^{+}(G)$ , the restriction of $\theta$ to $A^{+}(v)$ is a rotor order at $v$ . The directed multigraph $G$ combined with a rotor order $\theta$ is a rotor graph.

A rotor configuration of $G$ is a mapping from $\rho:V^{+}(G)\rightarrow A(G)$ such that $\rho(v)\in A^{+}(v)$ for each $v\in V^{+}(G)$ . Let $\mathcal{R}_{G}$ be the set of rotor configurations of $G$ . A particle configuration of $G$ is a mapping from $\sigma:V(G)\rightarrow\operatorname{\mathbb{Z}}$ . Let $\operatorname{\mathbb{Z}}^{V(G)}$ be the set of particle configurations of $G$ .

For node $v$ , denote by $\bm{v}\in\operatorname{\mathbb{Z}}^{V(G)}$ the function which is $1$ at $v$ , and $0$ elsewhere. For example, $\sigma^{\prime}=\sigma+3\bm{v}$ means $\sigma^{\prime}(v)=\sigma(v)+3$ and $\sigma^{\prime}(u)=\sigma(u)$ for $u\neq v$ .

A rotor-particle configuration of $G$ is a pair $(\rho,\sigma)$ of a rotor configuration $\rho\in\mathcal{R}_{G}$ and a particle configuration $\sigma\in\operatorname{\mathbb{Z}}^{V(G)}$ . Routing at $v\in V^{+}(G)$ on $(\rho,\sigma)$ is the operation of moving a particle from $v$ along the arc $\rho(v)$ and then changing the rotor configuration at $v$ to $\theta(\rho(v))$ . The resulting rotor-particle configuration $(\rho^{\prime},\sigma^{\prime})=\operatorname{rout}^{\bm{v}}(\rho,\sigma)$ is then formally defined as

\displaystyle\rho^{\prime}(u)

\displaystyle=\begin{cases}\theta(\rho(u))&u=v,\\ \rho(u)&u\neq v,\end{cases}

and $\sigma^{\prime}=\sigma+\operatorname{head}(\rho(v))-\operatorname{tail}(\rho(v))$ . Routing decomposes into two operators. First, a move at $v$ , denoted by $\phi(\rho;\bm{v})=\operatorname{head}(\rho(v))-\operatorname{tail}(\rho(v))$ . Second, a turn at $v$ , denoted by $\theta^{\bm{v}}$ , where $\theta^{\bm{v}}(a)=\theta(a)$ for each $a\in A^{+}(v)$ and $\theta^{\bm{v}}(a)=a$ for each $a\not\in A^{+}(v)$ . We see that

\displaystyle\operatorname{rout}^{\bm{v}}(\rho,\sigma)=(\theta^{\bm{v}}\circ% \rho,\sigma+\phi(\rho;\bm{v}))=(\rho^{\prime},\sigma^{\prime})\enspace.

This kind of routing is referred to as move-then-turn, as opposed to turn-then-move. It is easy to see that both kinds of routing are isomorphic by advancing or reverting the rotor configuration. We will use this isomorphism in the proof of 5.

We define $\theta^{-\bm{v}}=(\theta^{\bm{v}})^{-1}$ and $\phi(\rho;-\bm{v})=-\phi(\theta^{-\bm{v}}\circ\rho;\bm{v})$ ; the inverse of $\operatorname{rout}^{\bm{v}}$ is defined as

\displaystyle\operatorname{rout}^{-\bm{v}}(\rho^{\prime},\sigma^{\prime})=(% \theta^{-\bm{v}}\circ\rho^{\prime},\sigma^{\prime}+\phi(\rho^{\prime};-\bm{v})% )=(\rho,\sigma)\enspace.

Given distinct nodes $v\neq u$ , observe that $\operatorname{rout}^{\bm{v}}$ and $\operatorname{rout}^{\bm{u}}$ commute, as the move and turn of $v$ depend on and affect $\rho$ only at component $v$ . Hence, compositions of the routing operators are characterized by the number of times each node is routed.

A routing vector (or simply a routing) of $G$ is a mapping from $r:V^{+}(G)\rightarrow\mathbb{Z}$ . We denote by $\operatorname{rout}^{r}$ the operator resulting from composing all $(\operatorname{rout}^{\bm{v}})^{r(v)}$ for $v\in V^{+}(G)$ in arbitrary order. Similarly, we let $\theta^{r}$ denote the composition of all $(\theta^{\bm{v}})^{r(v)}$ for $v\in V^{+}(G)$ . Extending the move operator $\phi(\rho;\bm{v})$ is more involved. We do so by interpreting $\phi$ to be the displacement of particles when routing. As such, for $k\in\mathbb{N}$ , we define $\phi(\rho;k\bm{v})=\sum_{i=0}^{k-1}\phi(\theta^{i\bm{v}}\circ\rho;\bm{v})$ and $\phi(\rho;-k\bm{v})=-\sum_{i=1}^{k}\phi(\theta^{-i\bm{v}}\circ\rho;\bm{v})$ . Then we define $\phi(\rho;r)=\sum_{v\in V^{+}(G)}\phi(\rho;r(v)\bm{v})$ . It is now straightforward to see that

\displaystyle\operatorname{rout}^{r}(\rho,\sigma)

\displaystyle=(\theta^{r}\circ\rho,\sigma+\phi(\rho;r))\enspace.

For the sake of convenience, we extend these notations to sinks. Each routing $r\in\operatorname{\mathbb{Z}}^{V^{+}(G)}$ is identified with the mapping in $\operatorname{\mathbb{Z}}^{V(G)}$ such that $r(s)=0$ for all $s\in S_{0}$ . Furthermore, routing sinks has no effect, i.e., $\theta^{\bm{s}}=\operatorname{id}$ and $\phi(\rho;\bm{s})=\bm{0}$ .

2.3 Arrival and Rotor-Routing Games

In the Arrival game we start with a rotor-particle configuration $(\rho,\bm{u})$ where $u\in V^{+}(G)$ is the initial location of the particle. We then repeatedly route the node on which the particle is located. This makes the particle walk through the rotor graph until it ends up on a sink, at which point the game terminates. To ensure termination, throughout this article we require $G$ to be stopping, meaning that every node has a directed path to some sink.

We now introduce the rotor-routing game, which generalizes Arrival. We say that routing node $v$ is legal on $(\rho,\sigma)$ if $\sigma(v)>0$ . A routing sequence $(v_{0},\dots,v_{k-1})\in(V^{+}(G))^{k}$ is legal on $(\rho_{0},\sigma_{0})$ if each routing of $v_{i}$ is legal on $(\rho_{i},\sigma_{i})$ where $(\rho_{i+1},\sigma_{i+1})=\operatorname{rout}^{\bm{v_{i}}}(\rho_{i},\sigma_{i})$ . Finally, a non-negative routing $r$ is legal if there is a corresponding legal routing sequence $(v_{0},\dots,v_{k-1})$ , which means that $r(v)=\big{|}\{i\in\{0,\dots,k-1\}\mid v_{i}=v\}\big{|}$ for each $v\in V^{+}(G)$ .

Such a legal routing $r$ is maximal on $(\rho,\sigma)$ if $\sigma^{\prime}=\sigma+\phi(\rho;r)$ is non-positive on $V^{+}(G)$ . That is, a routing $r$ is maximal if no node can be legally routed after routing $r$ .

In the rotor-routing game, at each step an arbitrary legal node is routed until all particles are on sinks. It is easy to see that in Arrival, the legal routing sequence is unique, but in rotor-routing at any point there may be multiple nodes that can be legally routed.

An important consequence of routing a node behaving independent of the configuration of other nodes is that every legal routing sequence eventually terminates with the same corresponding maximal legal routing.

Lemma 3 ([9, Lemma 3.9]).

For all $(\rho,\sigma)\in\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}$ with $\sigma\geq\bm{0}$ , there is a unique maximal legal routing $r$ on $(\rho,\sigma)$ .

It follows that the maximal legal routing is an upper bound (component-wise) of all legal routings. We denote by $(\rho^{\prime},\sigma^{\prime})=\operatorname{rout}^{\infty}_{L}(\rho,\sigma)$ the rotor-particle configuration resulting from the unique maximal legal routing on $(\rho,\sigma)$ .

We are now ready to formally define the problems discussed in this paper through the notion of routings.

Problem (Arrival [3]).

Given $(\rho,\bm{u})\in\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}$ , compute $\sigma^{\prime}$ for $(\rho^{\prime},\sigma^{\prime})=\operatorname{rout}^{\infty}_{L}(\rho,\bm{u})$ .

The following generalization of Arrival was introduced by Hoang [8]:

Problem (Legal Multi-Arrival [8]).

Given $(\rho,\sigma)\in\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}$ with $\sigma\geq\bm{0}$ , compute $\sigma^{\prime}$ for $(\rho^{\prime},\sigma^{\prime})=\operatorname{rout}^{\infty}_{L}(\rho,\sigma)$ .

An even more general scenario was introduced by Auger et al. [1]. Namely, if we do not require routings to be legal, for arbitrary $\sigma$ any routing can be extended such that $\sigma^{\prime}(v)=0$ for all $v\in V^{+}(G)$ . Such a rotor-particle configuration is called fully routed. We denote by $\operatorname{rout}^{\infty}(\rho,\sigma)$ the set of fully routed rotor-particle configurations obtainable by routing $(\rho,\sigma)$ .

Proposition 4 ([1, Theorem 2]).

For all $(\rho,\sigma)\in\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}$ there is a routing $r$ such that with $(\rho^{\prime},\sigma^{\prime})=\operatorname{rout}^{r}(\rho,\sigma)$ one has $\sigma^{\prime}(v)=0$ on all $v\in V^{+}(G)$ . Furthermore, for any two such routings $r_{1}$ and $r_{2}$ , resulting in $(\rho^{1},\sigma^{1})$ and $(\rho^{2},\sigma^{2})$ , respectively, we have that $\sigma^{1}=\sigma^{2}$ .

This leads to the following problem, which is our main concern in this paper:

Problem (Multi-Arrival [1]).

Given $(\rho,\sigma)\in\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}$ , compute $\sigma^{\prime}$ for arbitrary $(\rho^{\prime},\sigma^{\prime})\in\operatorname{rout}^{\infty}(\rho,\sigma)$ .

For $\sigma\geq\bm{0}$ , after applying the maximal legal routing it holds that $\sigma^{\prime}(v)=0$ for $v\in V^{+}(G)$ . It follows that $\operatorname{rout}_{L}^{\infty}(\rho,\sigma)\in\operatorname{rout}^{\infty}(% \rho,\sigma)$ and that Legal Multi-Arrival reduces to Multi-Arrival. Conversely, finding full routings reduces to finding a maximal legal routing in $G$ and in $G^{(-1)}$ , where $G^{(-1)}$ is obtained from $G$ by reversing the rotor order i.e. using $\theta^{-1}$ .

Proposition 5.

Let $(\rho,\sigma)\in\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}$ and $\sigma=\sigma_{1}-\sigma_{2}$ such that $\sigma_{1},\sigma_{2}\geq\bm{0}$ . Then given the maximal legal routing $r_{1}$ on $(\rho,\sigma_{1})$ in $G$ and the maximal legal routing $r_{2}$ on $(\theta^{r_{1}-\bm{1}}\circ\rho,\sigma_{2})$ in $G^{(-1)}$ , we have that $r=r_{1}-r_{2}$ is a full routing on $(\rho,\sigma)$ in $G$ .

Proof.

We define $g\colon\mathcal{R}_{G}\times\operatorname{\mathbb{Z}}^{V(G)}\to\mathcal{R}_{G}% \times\operatorname{\mathbb{Z}}^{V(G)}$ by $g(\rho,\sigma)=(\theta^{-1}\circ\rho,-\sigma)$ . The function $g$ transforms rotor-particle configurations such that negative move-then-turn routings in $G$ correspond to positive turn-then-move routings in $G^{(-1)}$ . We let $\theta^{\prime}=\theta^{-1}$ and $\phi^{\prime}$ denote the move and displacement operators in $G^{(-1)}$ .

Claim.

It holds that $\operatorname{rout}^{r}_{G}(\rho,\sigma)=g^{-1}\bigl{(}{\operatorname{rout}}^{% -r}_{G^{(-1)}}(g(\rho,\sigma))\bigr{)}$ .

Proof.

We show that $\operatorname{rout}^{\bm{v}}_{G}(\rho,\sigma)=g^{-1}\bigl{(}{\operatorname{% rout}}^{-\bm{v}}_{G^{(-1)}}(g(\rho,\sigma))\bigr{)}$ , from which the claim follows. Recall that ${\operatorname{rout}}_{G^{(-1)}}^{-\bm{v}}(\rho,\sigma)=\bigl{(}\theta^{\prime% -\bm{v}}\circ\rho,\sigma-\phi(\theta^{\prime-\bm{v}}\circ\rho;\bm{v})\bigr{)}$ . First, for the turn operator we see that $\theta^{\prime-\bm{v}}\circ\theta^{-1}=\theta^{-1}\circ\theta^{\bm{v}}$ . Then, for the move operator we derive that

\displaystyle-\phi(\theta^{\prime-\bm{v}}\circ\theta^{-1}\circ\rho;\bm{v})

\displaystyle=-\phi(\rho;\bm{v})\enspace.

Consequently, it holds that

	$\displaystyle g^{-1}\bigl{(}{\operatorname{rout}}^{-\bm{v}}_{G^{(-1)}}(g(\rho,% \sigma))\bigr{)}$	$\displaystyle=g^{-1}\circ{\operatorname{rout}}^{-\bm{v}}_{G^{(-1)}}(\theta^{-1% }\circ\rho,-\sigma)$
		$\displaystyle=g^{-1}\circ\bigl{(}\theta^{-1}\circ\theta^{\bm{v}}\circ\rho,-% \sigma-\phi(\rho;\bm{v})\bigr{)}$
		$\displaystyle=\bigl{(}\theta^{\bm{v}}\circ\rho,\sigma+\phi(\rho;\bm{v})\bigr{)% }={\operatorname{rout}}^{\bm{v}}_{G}(\rho,\sigma)\enspace.$

This proves the claim. $\hfill\vartriangleleft$ We next find that $\sigma+\phi(\rho;r_{1}-r_{2})=(\sigma_{1}+\phi(\rho;r_{1}))-(\sigma_{2}+\phi^{% \prime}(\theta^{r_{1}-\bm{1}}\circ\rho;r_{2}))$ . Since $r_{1}$ is maximal on $(\rho,\sigma_{1})$ with $\sigma_{1}\geq\bm{0}$ in $G$ , it follows that $\sigma_{1}+\phi(\rho;r_{1})$ is $0$ on $V^{+}(G)$ . Similarly, as $r_{2}$ is maximal on $(\theta^{r_{1}-\bm{1}}\circ\rho,\sigma_{2})$ , with $\sigma_{2}\geq\bm{0}$ in $G^{(-1)}$ we have that $\sigma_{2}+\phi^{\prime}(\theta^{r_{1}-\bm{1}}\circ\rho;r_{2})$ is also $0$ on $V^{+}(G)$ . It follows that $r$ is a full routing. $\hfill\blacktriangleleft$

Our approach finds maximal legal routings which enables us to solve both Legal Multi-Arrival and Multi-Arrival on tree-like rotor graphs.

3 Routing Decompositions

In this section we show how to decompose maximal legal routings into legal routings whose most recently used arcs are directed towards sinks. We shall always denote the maximal legal routing by $\hat{r}$ , assuming some $(\rho,\sigma)$ to be fixed.

3.1 Destination Graphs

Given a rotor configuration $\rho$ and routing $r\geq\bm{0}$ , the destination graph $G[\rho;r]$ is a subgraph of $G$ whose nodes consist of all those that either sent or received particles during routing $r$ . For each node $v\in\operatorname{supp}(r)$ , that is $r(v)\neq 0$ , the destination graph $G[\rho;r]$ contains only the outgoing arc that the last particle traversing $v$ was sent over when routing $r$ . That is, $G[\rho;r]$ is the subgraph of $G$ induced by the arcs $\{\theta^{-1}(\rho^{\prime}(v))\mid v\in\operatorname{supp}(r)\}$ , where $\rho^{\prime}=\theta^{r}\circ\rho$ is the rotor configuration after routing $r$ . Each node $v\in\operatorname{supp}(r)$ has one outgoing arc in $G[\rho;r]$ and every other node in $G[\rho;r]$ has no outgoing arcs.

Furthermore, the destination graph $G[\rho;\hat{r}]$ of the maximal legal routing is acyclic and the connected components are directed subtrees rooted at sinks. Figure 1 depicts a rotor graph with the rotor order being clockwise, and a corresponding destination graph.

(a) On

(\rho,\sigma)

.

(b) On

(\rho^{\prime},\sigma^{\prime})

.

Figure 1: (a) A rotor graph

G

with a rotor-particle configuration

(\rho,\sigma)

, where solid lines represent

\rho

, labels on the nodes represent the particle distribution

\sigma=1\bm{v}_{2}+2\bm{v}_{3}

. A possible maximal legal routing sequence is

v_{2}\to v_{4}\to v_{2}\to s_{2}

,

v_{3}\to v_{4}\to v_{1}\to v_{2}\to v_{4}\to v_{2}\to s_{2}

and

v_{3}\to s_{3}

, with corresponding maximal legal routing

\hat{r}=1\bm{v}_{1}+4\bm{v}_{2}+2\bm{v}_{3}+3\bm{v}_{4}

. (b) Thick red lines are the arcs in the destination graph

G[\rho;\hat{r}]

for the maximal legal routing

\hat{r}

. Note that

G[\rho;\hat{r}]

does not contain

s_{1}

.

3.2 Compensated Routings

Any legal routing $r$ must satisfy the condition that, for each node $v$ , the number of particles sent out of $v$ during the routing process must not exceed the number of particles initially present at $v$ and those sent into $v$ during the routing. This establishes one of the main constraints for a routing to be legal. We call such a routing “compensated”.

Formally, we say that a routing $r$ is compensated at $v$ with respect to $(\rho,\sigma)$ if

\displaystyle\sigma(v)+\sum_{u\in N^{-}(v)}\phi^{u}_{v}(\rho;r(u))\geq\sum_{w% \in N^{+}(v)}\phi^{v}_{w}(\rho;r(v))=r(v),

where $\phi^{v}_{w}(\rho;j)$ denotes the number of particles sent to $w$ when routing $j$ particles out of $v$ .

A routing is called compensated if it is compensated at each $v\in V^{+}(G)$ . Equivalently, $r$ is compensated if and only if $\sigma+\phi(\rho;r)\geq\bm{0}$ . Note that compensated routings are not necessarily legal.

The following proposition, which is a special case of a theorem by Tóthmérész [11, Theorem 3.4], provides a characterization of compensated routings that are legal. For sake of completeness, we include a simplified proof.

Proposition 6.

Given a routing $r\geq\bm{0}$ and rotor-particle configuration $(\rho,\sigma)$ with $\sigma\geq\bm{0}$ . Let $(\rho^{\prime},\sigma^{\prime})=\operatorname{rout}^{r}(\rho,\sigma)$ . The routing $r$ is legal on $(\rho,\sigma)$ if and only if, $r$ is compensated on $(\rho,\sigma)$ and each cycle in $G[\rho;r]$ contains some node $v$ such that $\sigma^{\prime}(v)>0$ . In particular, if $G[\rho;r]$ is acyclic, legality and compensation are equivalent.

Proof.

Suppose that $r$ is legal. So it is compensated. If $G[\rho;r]$ contains a cycle $C$ , then given some corresponding legal routing sequence, there is some node $v\in V(C)$ that is routed last in $C$ . Let $w\in V(C)$ denote the successor of $v$ in $C$ . Then a particle is sent from $v$ to $w$ , but $w$ is not routed afterwards. Hence, as the particle distribution is non-negative during the legal routing sequence, we have that $\sigma^{\prime}(w)>0$ .

Conversely, assume that $r$ is compensated on $(\rho,\sigma)$ and each cycle in $G[\rho;r]$ contains some node $v$ such that $\sigma^{\prime}(v)>0$ . Let $r^{*}\leq r$ be a legal routing with $(\rho^{*},\sigma^{*})=\operatorname{rout}^{r^{*}}(\rho,\sigma)$ obtained by routing until for each node $v$ either $\sigma^{*}(v)=0$ or $r^{*}(v)=r(v)$ .

Since $r^{*}$ is legal, it suffices to show that $r^{*}=r$ . Assume, for the sake of contradiction, that $r^{*}\neq r$ . We then consider the set $B=\{v\in V^{+}(G)\mid r^{*}(v)<r(v)\}$ of nodes that still need to be routed (if any).

It follows that $\sigma^{*}(v)=0$ for each $v\in B$ . In the remaining routing $r^{*}-r$ , each particle sent out from a node in $B$ must be replaced afterward; otherwise, we would end up with a node $v\in B$ such that $\sigma^{\prime}(v)<0$ , which is impossible since $r$ is compensated. This implies that during the routing $r^{*}-r$ , no particle from $B$ is sent outside of $B$ ; otherwise, that particle could not be replaced in $B$ as no node outside of $B$ is routed in $r^{*}-r$ . It follows that in the subgraph $H$ of $G[\rho;r]$ induced by $B$ , the nodes have out-degree of 1, implying that $H$ contains a cycle. This contradicts the assumption that every cycle in $G[\rho;r]$ contains a node $v$ such that $\sigma^{\prime}(v)>0$ . $\hfill\blacktriangleleft$

3.3 $𝒔$ -Directed Routings

The compensated routings $r$ are those for which each $v\in V^{+}(G)$ satisfies an inequality that relates $r(v)$ to $r(u)$ for all in-neighbours $u$ of $v$ . Enforcing this inequality is much simpler than enforcing the stricter property of legality. If restricted to routings with acyclic destination graph, these properties coincide. For finding the maximal legal routing $\hat{r}$ , we may restrict the search to only those routings. But the destination graph being acyclic is also a non-trivial property. Instead, we consider an even more restricted case in which the destination graph is oriented towards some fixed sink $s$ . In tree-like rotor graphs, this implies a unique destination graph (up to parallel arcs), which can be enforced by an appropriate parametrization of routings. But first, we need to show that these restricted routings still allow us to recover $\hat{r}$ .

Given a rotor configuration $\rho$ and sink $s$ , we say that node $v$ is $s$ -directed in a routing $r$ if $v\in\operatorname{supp}(r)$ and there is a path in $G[\rho;r]$ from $v$ to $s$ . Routing $r$ is $s$ -directed if every $v\in\operatorname{supp}(r)$ is $s$ -directed in $r$ . Our aim, to be established in Theorem 9, is to decompose $\hat{r}$ into a set of $s$ -directed routings $r_{s}$ for each sink $s$ . The idea is that each such $r_{s}$ need only match the number of particles sent into $s$ by $\hat{r}$ . We denote by $\phi_{w}(\rho;r)$ the number of particles sent to $w$ when routing $r$ .

Lemma 7.

Let $(\rho,\sigma)$ be a rotor-particle configuration with $\sigma\geq\bm{0}$ and $b\geq\bm{0}$ be a legal routing. Then, for each sink $s$ , there is an $s$ -directed legal routing $r\geq\bm{0}$ such that $r\leq b$ and $\phi_{s}(\rho;r)=\phi_{s}(\rho;b)$ .

Proof.

We construct a series of legal routings $b=r_{1}\geq r_{2}\geq\cdots$ with $A_{1}\subset A_{2}\subset\cdots$ denoting the $s$ -directed nodes of the respective routing, such that each $r_{i+1}$ equals $r_{i}$ on $A_{i}$ and each $v\in A_{i}$ has the same in-flow in $r_{i+1}$ as in $r_{i}$ .

Suppose that we constructed $r_{i}$ and that there is flow from $V^{+}(G)\setminus A_{i}$ to $A_{i}$ when routing $r_{i}$ . Consider an arbitrary legal routing sequence $(v_{0},\dots,v_{m-1})$ corresponding to $r_{i}$ with $(\rho_{0},\sigma_{0})=(\rho,\sigma)$ and $(\rho_{\ell+1},\sigma_{\ell+1})=\operatorname{rout}^{\bm{v_{\ell}}}(\rho_{\ell% },\sigma_{\ell})$ .

Let $j$ be maximal such that $v_{j}\not\in A_{i}$ and $\operatorname{head}(\rho_{j}(v_{j}))\in A_{i}$ . That is, the $j^{\textnormal{th}}$ routing step is the last time a particle is sent into $A_{i}$ from $V^{+}(G)\setminus A_{i}$ . Now, we remove each routing step $\ell>j$ with $v_{\ell}\not\in A_{i}$ . Let $r_{i+1}$ be the corresponding routing vector. Then $r_{i+1}$ must be legal since for $\ell>j$ we have $v_{\ell}\in A_{i}$ and $v_{\ell}$ has in the $\ell$ -th routing step the same number of particles as before the removals. By construction $r_{i+1}$ satisfies the required conditions and $A_{i}\cup\{v_{j}\}\subseteq A_{i+1}$ as $v_{j}$ sent its last particle towards $A_{i}$ in $r_{i+1}$ .

Otherwise, suppose there is no flow from $V^{+}(G)\setminus A_{i}$ to $A_{i}$ when routing $r_{i}$ . We set $r$ to be $r_{i}$ on $A_{i}$ , and zero on $V^{+}(G)\setminus A_{i}$ . Then $r$ is an $s$ -directed legal routing with $r\leq r_{1}=b$ . Since $s\in A_{1}\subseteq A_{2}\subseteq\dots$ we have $\phi_{s}(\rho;r_{1})=\phi_{s}(\rho;r_{2})=\cdots=\phi_{s}(\rho;r)$ . This procedure is finite as it terminates once $\operatorname{supp}(b)\subseteq A_{i}$ and each step increases the size of $A_{i}$ . $\hfill\blacktriangleleft$

Next, we show that in the maximal legal routing $\hat{r}$ the $s$ -directed nodes already route only as much as is required to achieve the flow towards $s$ . We therefore derive that a corresponding $s$ -directed routing matches $\hat{r}$ on those nodes.

Lemma 8.

Let $(\rho,\sigma)$ be a rotor-particle configuration with $\sigma\geq\bm{0}$ . If $r\geq\bm{0}$ is an $s$ -directed legal routing such that $\phi_{s}(\rho;r)=\phi_{s}(\rho;\hat{r})$ , then $r(v)=\hat{r}(v)$ for each $s$ -directed node of $\hat{r}$ .

Proof.

Suppose $u$ is $s$ -directed in $\hat{r}$ such that $r(u)\neq\hat{r}(u)$ . We denote by $v$ the successor on the path from $u$ to $s$ in $G[\rho;\hat{r}]$ . As $\hat{r}$ is maximal and $r$ is legal, it must be that $r(u)<\hat{r}(u)$ . Since the last particle sent from $u$ in $\hat{r}$ is towards $v$ we have $\phi^{u}_{v}(\rho;r(u))<\phi^{u}_{v}(\rho;\hat{r}(u))$ . In particular, $\phi_{v}(\rho;r)<\phi_{v}(\rho;\hat{r})$ . If $v\neq s$ , then as $\hat{r}$ routes $v$ for each received particle and $r$ receives less particles on $v$ , it follows that $r(v)<\hat{r}(v)$ . Now, $v$ is also $s$ -directed in $\hat{r}$ with $r(v)\neq\hat{r}(v)$ . We repeat the argument along the path from $u$ to $s$ in $G[\rho;\hat{r}]$ until we end up with $v=s$ . Then $\phi_{s}(\rho;r)<\phi_{s}(\rho;\hat{r})$ contradicts the assumption that $\phi_{s}(\rho;r)=\phi_{s}(\rho;\hat{r})$ . $\hfill\blacktriangleleft$

Theorem 9.

Let $(\rho,\sigma)$ be a rotor-particle configuration with $\sigma\geq\bm{0}$ . For each $s\in S_{0}$ , let $r_{s}$ be an optimal solution of the following optimization problem:

maximize

\displaystyle\phi_{s}(\rho;r)\qquad\text{subject to}\;\quad\quad

\displaystyle r\;\text{is an $s$-directed compensated routing}.

Then $\hat{r}$ is given by $\hat{r}(v)=\max\{r_{s}(v)\mid s\in S_{0}\}$ for all $v\in V^{+}(G)$ .

Proof.

Let $s\in S_{0}$ . As $r_{s}$ is $s$ -directed, it has an acyclic destination graph. Since it is also compensated, it follows from 6 that $r_{s}$ is legal. In particular, as $\hat{r}$ is maximal we have $r_{s}\leq\hat{r}$ and $\phi_{s}(\rho;r_{s})\leq\phi_{s}(\rho;\hat{r})$ . Now, as shown by 7 there is some legal $s$ -directed routing $r^{\prime}_{s}$ such that $\phi_{s}(\rho;r^{\prime}_{s})=\phi_{s}(\rho;\hat{r})$ . It follows from $r_{s}$ maximizing $\phi_{s}(\rho;r)$ that $\phi_{s}(\rho;r_{s})=\phi_{s}(\rho;\hat{r})$ .

For each $v\not\in\operatorname{supp}(\hat{r})$ the claim holds as $0\leq r_{s}(v)\leq\hat{r}(v)=0$ for each $s\in S_{0}$ . Let $v\in\operatorname{supp}(\hat{r})$ . Then as $G[\rho;\hat{r}]$ is acyclic and each node in $G[\rho;\hat{r}]$ has out-degree at most one, there is some $u$ that the unique path starting at $v$ ends on. If $u\not\in S_{0}$ , then $u\not\in\operatorname{supp}(\hat{r})$ . But then $u$ receives a particle in $\hat{r}$ but is not routed, which contradicts the maximality of $\hat{r}$ . Thus, $u\in S_{0}$ and $v$ is $u$ -directed in $\hat{r}$ . Consequently, due to 8 we find that $\hat{r}(v)=r_{u}(v)=\max\{r_{s}(v)\mid s\in S_{0}\}$ . $\hfill\blacktriangleleft$

4 Algorithms for Multi-Arrival on Tree-Like Rotor Graphs

In the following, let $T$ be a tree-like rotor graph. Henceforth assume, without loss of generality, that the induced subgraph of $T$ on $V^{+}(T)$ is strongly connected, and each sink to have exactly one in-neighbour. Indeed, if $T$ were not strongly connected, then we can solve Multi-Arrival in some ordering of the strongly connected components as each component has no particles flowing to the prior. Furthermore, if some sink had multiple in-neighbours, we split it into one sink per in-neighbor.

4.1 Relative Rotor Subgraphs

With the above assumptions on $T$ , each $v\in V^{+}(T)$ has a unique successor on its paths to $s$ in $T$ . We denote by $N^{+}_{s}(v)$ the successor on the paths from $v$ to $s$ in $T$ , and by $N^{-}_{s}(v)$ the set of predecessors whose successor is $v$ on their respective paths towards $s$ . When a routing is $s$ -directed, its destination graph can be seen to be an $s$ -rooted directed subtree of $T$ .

Throughout this section, we fix a sink $s\in S_{0}$ and a rotor-particle configuration $(\rho,\sigma)$ with $\sigma\geq\bm{0}$ . For the sake of convenience, we leave this dependence on $s$ and $(\rho,\sigma)$ implicit in the introduced notation. Further, we simplify the notation and let $\phi(r)$ denote $\phi(\rho;r)$ , and similarly extend this simplification to $\phi^{v}_{w}$ and $\phi_{v}$ .

We proceed to show that $s$ -directed routings can be characterized by their restrictions to nested rotor subgraphs. For any node $v\in V^{+}(T)$ with $w=N^{+}_{s}(v)$ let $T_{v}$ be the rotor graph obtained from $T$ as follows. We remove the arcs between $v$ and $w$ , and then, remove the nodes not reachable from $v$ . Finally, we add $w$ again with only the original arcs from $v$ to $w$ (but not the reverse arcs). In $T_{v}$ , node $w$ is thus a sink. See Figure 2 for an example.

Figure 2: Example of a relative subtree

T_{v}

. Grey dashed lines show the arcs oriented away from

s

. Note that, e.g., the rotor graph

T_{v_{2}}

contains

v_{1}

as a sink, which therefore has no arcs from

v_{1}

to

v_{2}

.

For any integers $x,y\in\mathbb{N}$ , we denote by $H_{v}(x,y)$ the set of $w$ -directed compensated routings $r$ in $T_{v}$ on rotor-particle configuration $(\rho,\sigma+y\bm{v})$ such that $\phi^{v}_{w}(r(v))=x$ .

Furthermore, we define $h_{v}(y)=\max\{x\in\mathbb{N}\mid H_{v}(x,y)\neq\emptyset\}$ .

Note that for a given $y$ , from 7 it follows that $h_{v}(y)$ is the flow from $v$ to $w$ that is legally achievable in $T_{v}$ when dispersing an additional $y$ particles on $v$ .

Lemma 10.

Given $v\in V^{+}(T)$ and $x,y\in\mathbb{N}$ such that $H_{v}(x,y)\neq\emptyset$ , we have $H_{v}(x^{\prime},y)\neq\emptyset$ for any $0\leq x^{\prime}\leq x$ . In particular, $H_{v}(x,y)\neq\emptyset$ if and only if $0\leq x\leq h_{v}(y)$ .

Proof.

Let $r\in H_{v}(x,y)$ and let $b$ be some legal routing such that $x^{\prime}=\phi_{w}(\rho;b)\leq\phi_{w}(\rho;r)=x$ in $T_{v}$ , where $w=N^{+}_{s}(v)$ . Note that such a $b$ exists as we may truncate a legal routing sequence of $r$ up to the $x^{\prime}$ -th routing towards $w$ . Then, using 7 with $b$ on $T_{v}$ , we obtain an $w$ -directed compensated routing $r^{\prime}$ with $x^{\prime}=\phi_{w}(\rho;r^{\prime})$ . Hence, $r^{\prime}\in H_{v}(x^{\prime},y)$ . As the zero routing is always compensated and $s$ -directed, the second claim follows as well. $\hfill\blacktriangleleft$

Let $w=N^{+}_{s}(v)$ and $u\in N^{-}_{s}(v)$ . We define the function $q_{v}\colon\mathbb{N}\to\mathbb{N}$ as the minimum number of routings required to send $x$ particles from $v$ to $w$ . Formally, $q_{v}(x)=\min\{k\in\mathbb{N}\mid\phi^{v}_{w}(\rho;k)=x\}$ . It is also convenient to specify the notation $q^{v}_{u}(x)=\phi^{v}_{u}(q_{v}(x)),$ which is the number of particles that $v$ sends to $u$ as a by-product.

The following crucial lemma will enable us to recursively construct routings in $H_{v}(x,y)$ .

Lemma 11.

Let $v\in V^{+}(T)$ and $w=N^{+}_{s}(v)$ . Consider a routing $r\geq\bf 0$ on $T_{v}$ and for $u\in N^{-}_{s}(v)$ let $r_{u}$ denote the restriction of $r$ on $V^{+}(T_{u})$ . Then, $H_{v}(0,y)=\{\bm{0}\}$ , and for $x>0$ ,

\displaystyle r\in H_{v}(x,y)

if and only if

\displaystyle r(v)

\displaystyle=q_{v}(x),

(1)

and there exist non-negative integers $x_{u}$ , for $u\in N^{-}_{s}(v)$ , such that

	$\displaystyle\sum_{u\in N^{-}_{s}(v)}x_{u}$	$\displaystyle\geq r(v)-y-\sigma(v),$		(2)
	$\displaystyle r_{u}$	$\displaystyle\in H_{u}\bigl{(}x_{u},\phi^{v}_{u}(r(v))\bigr{)},\;\text{for % each $u\in N^{-}_{s}(v)$ \enspace.}$		(3)

In particular, $H_{v}(x,y)\neq\emptyset$ if and only if

\sum_{u\in N^{-}_{s}(v)}h_{u}(q^{v}_{u}(x))\geq q_{v}(x)-y-\sigma(v)\enspace.

(4)

Proof.

Let $r\in H_{v}(0,y)$ . Then $r(v)=0$ , as $\phi^{v}_{w}(r(v))=0$ and $r$ is $w$ -directed. It follows that $v$ is not in $T_{v}[\rho;r]$ , and since every path from $V^{+}(T_{v})$ to $w$ in $T_{v}$ is through $v$ , it must be that $\operatorname{supp}(r)=\emptyset$ .

Now, for the case $x>0$ , assume that $r\in H_{v}(x,y)$ and therefore $r(v)>0$ . Thus, the last routing of $r$ at $v$ should be towards $w$ , which is equivalent to (1).

Set $x_{u}=\phi^{u}_{v}(r_{u}(u))=\phi^{u}_{v}(r(u))$ . Then we see that (2) is a rearrangement of $r$ being compensated at $v$ . For (3), consider $u\in N^{-}_{s}(v)$ . As the nodes of $T_{u}$ are $w$ -directed in $r$ and their paths towards $w$ in $T_{v}[\rho;r]$ go through $v$ , it follows that $r_{u}$ is $v$ -directed in $T_{u}$ . It remains to show that $r_{u}$ being compensated in $T_{v}$ is equivalent to $r_{u}$ being compensated in $T_{u}$ . With $y_{u}=\phi^{v}_{u}(r(v))$ , note that $r_{u}$ needs to be compensated on $(\rho,\sigma+y_{u}\bm{u})$ in $T_{u}$ . Clearly, the only non-trivial case is the compensation at $u$ , which follows from the in-flow being equal in both cases:

\displaystyle\phi_{u}(r)

\displaystyle=\phi_{u}(r_{u})+\phi^{v}_{u}(r(v))+\sigma(u)=\phi_{u}(r_{u})+% \sigma(u)+y_{u}\enspace.

Consequently, $r_{u}\in H_{u}(x_{u},y_{u})$ .

Now suppose that $r\geq\bf 0$ is a routing that satisfies (1)–(3). Notably, as $x>0$ we have $q_{v}(x)>0$ . As mentioned above, (1) is equivalent to $v$ being $w$ -directed in $r$ . From (3) it follows that $x_{u}=\phi^{u}_{v}(r(u))$ , which together with (2) implies that $r$ is compensated at $v$ . Also, $r$ is $w$ -directed and compensated on $V^{+}(T_{v})\setminus\{v\}$ , because by (3), each restriction $r_{u}$ is $v$ -directed and compensated. $\hfill\blacktriangleleft$

The following properties of the functions $h_{v}$ are needed in our argument.

Lemma 12.

For any $v\in V^{+}(T)$ , define $f_{v}(x)=q_{v}(x)-\sigma(v)-\sum_{u\in N^{-}_{s}\!(v)}h_{u}(q^{v}_{u}(x))$ for all $x$ . Then the following properties hold for the functions $f_{v}$ and $h_{v}$ :

(i)

$h_{v}(y)=\max\{x\in\mathbb{N}\mid f_{v}(x)\leq y\}$ ,
(ii)

$h_{v}(y)\leq h_{v}(y+1)\leq h_{v}(y)+1$ , for $y\in\mathbb{N}$ ,
(iii)

$f_{v}(x+1)\geq f_{v}(x)+1$ , for $x\in\mathbb{N}$ .

Proof.

(i) We know that $h_{v}(y)$ equals the largest $x$ with $H_{v}(x,y)\neq\emptyset$ , which, by 11, is the largest $x$ satisfying (4), that is, the largest $x$ such that $f_{v}(x)\leq y$ .

(ii) Let $\hat{r}_{y}$ denote the maximal legal routing in $T_{v}$ on $(\rho,\sigma+y\bm{v})$ . Then, by definition of $h_{v}(y)$ and 7, we see that $h_{v}(y)=\phi_{w}(\rho;\hat{r}_{y})$ . Thus, with $h_{v}(y+1)=\phi_{s}(\rho;\hat{r}_{y+1})$ , we see that $h_{v}(y+1)=h_{v}(y)+1$ if that additional particle ends up in $w$ and $h_{v}(y+1)=h_{v}(y)$ otherwise.

(iii) Being integer-valued function, it suffices to show that $f_{v}$ is strictly increasing.

Observe that $q_{v}(x+1)-q_{v}(x)$ is the number of arcs until and including the next that has head $w$ . But $q^{v}_{u}(x+1)-q^{v}_{u}(x)$ is then the number of those arcs that have head $u$ . Consequently, $q_{v}(x+1)-q_{v}(x)>\sum_{u\in N^{-}_{s}\!(v)}\bigl{(}q^{v}_{u}(x+1)-q^{v}_{u}% (x)\bigr{)}$ , where by (ii), the right-hand side is as large as $\sum_{u\in N^{-}_{s}\!(v)}\bigl{(}h(q^{v}_{u}(x+1))-h(q^{v}_{u}(x))\bigr{)}$ . It then follows that $f_{v}(x+1)>f_{v}(x)$ . $\hfill\blacktriangleleft$

4.2 MULTI-ARRIVAL for Tree-Like Multigraphs

In this subsection, we prove the main result of the paper, 1. To do so, we first need to specify how a rotor graph is computationally represented.

Suppose we wanted to represent $A^{+}(v)$ and $\theta^{v}$ . We could take in a sequence of nodes $w_{1},\dots,w_{k}$ and let each index $i$ identify an outgoing arc with head $w_{i}$ . Arc with label $i$ is taken to be before $i+1$ in $\theta^{v}$ with index $k+1$ wrapping around to $1$ . We can improve upon this by merging consecutive duplicates $w_{i}=w_{i+1}$ by associating with each $w_{i}$ the number of times that entry is repeated. We denote by $\hat{A}$ the reduced arc set of the rotor graph obtained by removing arcs in $A$ that vanish due to this encoding of consecutive parallel arcs. This encoding is called succinct [4, 11]. Hence, $|\hat{A}|$ is polynomial in the input size, while $|A|$ may be exponential in the input size.

For a rooted simple tree $R$ , its contracted height $\operatorname{{\mathsf{ch}}}(R)$ is defined as the minimum height over all trees which are obtained from $R$ by contracting, for each node $v$ of $R$ , one of the arcs to its children.

Lemma 13.

For any rooted simple tree $R$ , it holds that $\operatorname{{\mathsf{ch}}}(R)\leq\log(1+\ell(R))$ , where $\ell(R)$ is the number of nodes of $R$ with at least two children.

Proof.

We proceed by induction on the height of $R$ ; recall that the height of a rooted tree is the maximum length of a path from its root to any of its other nodes. If the height of $R$ is zero, the assertion holds trivially. Thus, assume now that the height of $R$ is at least $1$ . Let $R_{1},\ldots,R_{k}$ be the connected components of $R$ after removing its root, with $\operatorname{{\mathsf{ch}}}(R_{j})=\max\{\operatorname{{\mathsf{ch}}}(R_{i})% \mid i=1,\ldots,k\}$ . If there is a unique such $j$ , then $\operatorname{{\mathsf{ch}}}(R)=\operatorname{{\mathsf{ch}}}(R_{j})$ since the edge to that subtree can be contracted, and we are thus done by the induction hypothesis.

Otherwise, there is another such $j$ , say $j^{\prime}$ . We may assume that $\ell(R_{j})\leq\ell(R_{j^{\prime}})$ . Then

\displaystyle\operatorname{{\mathsf{ch}}}(R)

\displaystyle\leq 1+\operatorname{{\mathsf{ch}}}(R_{j})\leq\log(2+2\ell(R_{j})% )\leq\log(1+\ell(R))\enspace.\

$\hfill\blacktriangleleft$

Let $R^{\prime}_{u}$ be the tree $\langle T[V^{+}]\rangle$ rooted at $u$ . We define

\displaystyle k(T)=1+\max\{\operatorname{{\mathsf{ch}}}(R^{\prime}_{u})\mid u% \in N^{-}(S_{0})\}\enspace.

By 13, $k(T)\leq 1+\log(n_{>2}(\langle T\rangle)+1)$ , where $n_{>2}(\langle T\rangle)$ denotes the number of nodes in $\langle T\rangle$ that have more than two neighbors.

Notice that $k(T)\leq\kappa(T)$ , where $\kappa(T)$ is the upper bound on the contracted heights of $\langle T\rangle$ as mentioned in introduction for the sake of stating an informal version of the main result.

We can thus now state our main result formally.

Theorem 1.

Multi-Arrival can be solved on any tree-like rotor graph $T$ with arc set $A$ in time $\mathcal{O}\Bigl{(}|S_{0}||\hat{A}|\log^{k}(|A|)\Bigr{)},$ where $k=k(T)\leq 1+\log\bigl{(}n_{>2}(\langle T\rangle)+1\bigr{)}$ . In particular, Multi-Arrival can be solved in time polynomial in $|A|$ if $k=\mathcal{O}\left(\frac{\log|A|}{\log(\log|A|)}\right)$ . Furthermore, if $k=\mathcal{O}(1)$ (which includes path-like rotor graphs as then $k=1$ ), Multi-Arrival can be solved in time polynomial in $|\hat{A}|$ .

Furthermore, in the procedure, a full routing for Multi-Arrival is obtained.

When $k$ is fixed, we have that $\log^{k}(|A|)\leq f(k)|A|$ for some computable function $f$ , and thus the run time of our algorithm would be at most $f(k)|A|^{3}$ . Therefore, we conclude:

Corollary 14.

Multi-Arrival on tree-like rotor graphs is fixed-parameter tractable with parameter $k$ .

One of the main ingredients of our approach is an affine approximation for the function $h_{v}(y)$ , which is provided by the following lemma:

Lemma 15.

For any $v\in V^{+}(T)$ , there is an affine function $\overline{h}_{v}\colon\mathbb{R}\to\mathbb{R}$ such that

|\overline{h}_{v}(y)-h_{v}(y)|\leq 2|A(T_{v})|,\quad y\in\mathbb{N}\enspace.

(5)

A set of these functions $\{\overline{h}_{v}\mid v\in V^{+}(T)\}$ can be determined in time $\mathcal{O}(|\hat{A}|)$ .

Proof.

We first observe that for $x>0$ , it holds that

	$\displaystyle q_{v}\bigl{(}x+d(v,w)\bigr{)}$	$\displaystyle=q_{v}(x)+d_{+}(v),$
	$\displaystyle q^{v}_{u}\bigl{(}x+d(v,w)\bigr{)}$	$\displaystyle=q^{v}_{u}(x)+d(v,u)\enspace.$

These properties suggest the following approximations:

	$\displaystyle\overline{q}_{v}(x)$	$\displaystyle=\bigl{(}d_{+}(v)-q_{v}(d(v,w))\bigr{)}+\frac{xd_{+}(v)}{d(v,w)}% \quad\hbox{to approximate $q_{v}(x)$, and}$
	$\displaystyle\overline{q}^{v}_{u}(x)$	$\displaystyle=\bigl{(}d(v,u)-q^{v}_{u}(d(v,w))\bigr{)}+\frac{xd(v,u)}{d(v,w)}% \quad\hbox{to approximate}\leavevmode\nobreak\ q^{v}_{u}(x)\enspace.$

Let $x=\ell d(v,w)+t\geq d(v,w)$ with $0\leq t<d(v,w)$ . Then

	$\displaystyle\left\|q_{v}(x)-\overline{q}_{v}(x)\right\|$	$\displaystyle=\left\|\bigl{(}q_{v}(d(v,w)+t)-q_{v}(d(v,w))\bigr{)}-\frac{td_{+}% (v)}{d(v,w)}\right\|<d_{+}(v),$		(6)
	$\displaystyle\left\|q^{v}_{u}(x)-\overline{q}^{v}_{u}(x)\right\|$	$\displaystyle=\left\|\bigl{(}q^{v}_{u}(d(v,w)+t)-q^{v}_{u}(d(v,w))\bigr{)}-% \frac{td(v,u)}{d(v,w)}\right\|<d(v,w)\enspace.$		(7)

Similarly, (6) and (7) hold for $x<d(v,w)$ as then $q_{v}(x)$ and $\overline{q}_{v}(x)$ lie within an interval of size $d_{+}(v)$ , and $q^{v}_{u}(x)$ and $\overline{q}^{v}_{u}(x)$ lie within an interval of size $d(v,w)$ . Now, define inductively

	$\displaystyle\overline{h}_{v}(y)$	$\displaystyle=\max\{x\in\mathbb{R}\mid\overline{f}_{v}(x)\leq y\},$
	$\displaystyle\overline{f}_{v}(x)$	$\displaystyle=\overline{q}_{v}(x)-\sigma(v)-\sum_{u\in N^{-}_{s}\!(v)}% \overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x)\bigr{)}\enspace.$

Claim.

For any $x,y,\delta\in\mathbb{R}$ with $\delta>0$ , it holds that

	$\displaystyle\overline{f}_{v}(x+\delta)$	$\displaystyle\geq\overline{f}_{v}(x)+\delta,$		(8)
	$\displaystyle\overline{h}_{v}(y+\delta)$	$\displaystyle\leq\overline{h}_{v}(y)+\delta\enspace.$		(9)

Proof.

We first observe that for each node $v$ , (9) follows from (8). Let $\overline{h}_{v}(y)=x$ . So $\overline{f}_{v}(x)=y$ . Then $\overline{f}_{v}(x+\delta)\geq\overline{f}_{v}(x)+\delta=y+\delta$ . As $\overline{f}_{v}$ is strictly increasing, we must have $\overline{h}_{v}(y+\delta)\leq x+\delta=\overline{h}_{v}(y)+\delta$ .

Now, we establish (8) by induction. We have that

\displaystyle\overline{f}_{v}(x+\delta)-\overline{f}_{v}(x)

\displaystyle=\overline{q}_{v}(x+\delta)-\overline{q}_{v}(x)-\sum_{u\in N^{-}_% {s}\!(v)}\Bigl{(}\overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x+\delta)\bigr{)% }-\overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x)\bigr{)}\Bigr{)}\enspace.

If $N^{-}_{s}\!(v)=\emptyset$ , then $\overline{f}_{v}(x+\delta)-\overline{f}_{v}(x)\geq\frac{\delta d_{+}(v)}{d(v,w% )}\geq\delta$ . Next, assume that $N^{-}_{s}\!(v)\neq\emptyset$ and (8) holds for all $u\in N^{-}_{s}\!(v)$ . Then by the above argument, (9) also holds for $u\in N^{-}_{s}\!(v)$ , implying that

\displaystyle\overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x+\delta)\bigr{)}-% \overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x)\bigr{)}

\displaystyle=\overline{h}_{u}\left(\overline{q}^{v}_{u}(x)+\frac{\delta d(v,u% )}{d(v,w)}\right)-\overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x)\bigr{)}\leq% \frac{\delta d(v,u)}{d(v,w)}\enspace.

It follows that $\overline{f}_{v}(x+\delta)-\overline{f}_{v}(x)\geq\frac{\delta d_{+}(v)}{d(v,w% )}-\sum_{u\in N^{-}_{s}\!(v)}\frac{\delta d(v,u)}{d(v,w)}=\delta$ , as required. $\hfill\vartriangleleft$

Claim 16.

If for all $x\in\operatorname{\mathbb{Z}}$ , $|\overline{f}_{v}(x)-f_{v}(x)|\leq L$ , then $|\overline{h}_{v}(y)-h_{v}(y)|\leq L+1$ for all $y\in\operatorname{\mathbb{Z}}$ .

Proof.

Suppose that $\overline{h}_{v}(y)=x$ . Then $\overline{f}_{v}(\lfloor x\rfloor)\leq\overline{f}_{v}(x)\leq y$ and $\overline{f}_{v}(\lfloor x\rfloor+1)>y$ . Thus, $f_{v}(\lfloor x\rfloor+1+L)\geq f_{v}(\lfloor x\rfloor+1)+L\geq\overline{f}_{v% }(\lfloor x\rfloor+1)$ , that is $f_{v}(\lfloor x\rfloor+1+L)>y$ . That means $h_{v}(y)\leq\lfloor x\rfloor+L$ . On the other hand, $f_{v}(\lfloor x\rfloor-L)\leq f_{v}(\lfloor x\rfloor)-L\leq\overline{f}_{v}(% \lfloor x\rfloor)\leq y$ . So $h_{v}(y)\geq\lfloor x\rfloor-L$ , and thus $\big{|}h_{v}(y)-\lfloor x\rfloor\big{|}\leq L$ which implies that $|h_{v}(y)-\overline{h}_{v}(y)|\leq L+1$ . $\hfill\vartriangleleft$

Now, we complete the proof by induction. If $N^{-}_{s}\!(v)=\emptyset$ , then $\overline{h}_{v}(y)=\frac{d(v,w)}{d_{+}(v)}(y+\sigma(v))$ is an affine function that satisfies (5), because of (6) and 16.

So assume that $N^{-}_{s}\!(v)\neq\emptyset$ and the assertion holds for $\overline{h}_{u}(y)$ for every $u\in N^{-}_{s}\!(v)$ . The property of being an affine function follows directly from the definition of $\overline{h}_{v}(y)$ .

For an integer $x$ , we have:

\displaystyle\left|h_{u}\bigl{(}q^{v}_{u}(x)\bigr{)}-\overline{h}_{u}\bigl{(}% \overline{q}^{v}_{u}(x)\bigr{)}\right|\leq\left|h_{u}\bigl{(}q^{v}_{u}(x)\bigr% {)}-\overline{h}_{u}\bigl{(}q^{v}_{u}(x)\bigr{)}\right|+\left|\overline{h}_{u}% \bigl{(}q^{v}_{u}(x)\bigr{)}-\overline{h}_{u}\bigl{(}\overline{q}^{v}_{u}(x)% \bigr{)}\right|\enspace.

(10)

The induction hypothesis implies that

\displaystyle\left|h_{u}\bigl{(}q^{v}_{u}(x)\bigr{)}-\overline{h}_{u}\bigl{(}q% ^{v}_{u}(x)\bigr{)}\right|

\displaystyle\leq 2|A(T_{u})|\enspace.

Combining (7) and (9), we see that

\displaystyle\left|\overline{h}_{u}\bigl{(}q^{v}_{u}(x)\bigr{)}-\overline{h}_{% u}\bigl{(}\overline{q}^{v}_{u}(x)\bigr{)}\right|

\displaystyle\leq d(v,u)\enspace.

Thus, the right-hand side of (10) is at most $d(v,u)+2|A(T_{u})|$ . It follows that for every $x\in\operatorname{\mathbb{Z}}$ , it holds that

\displaystyle|\overline{f}_{v}(x)-f_{v}(x)|\leq d_{+}(v)+\sum_{u\in N^{-}_{s}% \!(v)}\bigl{(}d(v,u)+2|A(T_{u})|\bigr{)}\enspace.

Then applying 16, for every $y\in\operatorname{\mathbb{Z}}$ we have that

\displaystyle|\overline{h}_{v}(y)-h_{v}(y)|\leq 1+d_{+}(v)+\sum_{u\in N^{-}_{s% }\!(v)}\bigl{(}d(v,u)+2|A(T_{u})|\bigr{)}\leq 2|A(T_{v})|\enspace.

The inductive constructing of $\overline{h}_{v}$ for each $v\in V^{+}(T)$ can be done in time $\mathcal{O}(|\hat{A}^{+}(v)|)$ . Therefore, the set $\{\overline{h}_{v}\mid v\in V^{+}(T)\}$ can be constructed in time $\mathcal{O}(|\hat{A}^{+}|)$ . $\hfill\blacktriangleleft$

In following, we let $k_{v}=1+\operatorname{{\mathsf{ch}}}(T^{\prime}_{v})$ where $T^{\prime}_{v}$ is the rooted simple tree $\langle T_{v}\rangle-(S_{0}\setminus\{s\})$ rooted at $w$ .

Lemma 17.

Let $t$ be the unique in-neighbour of $s$ . Then the maximum $\phi_{s}(r)$ over every $s$ -directed compensated routing $r$ can be obtained in time $\mathcal{O}\bigl{(}|\hat{A}|\log^{k_{t}}(|A|)\bigr{)}$ .

Proof.

We first determine the set of affine functions $\{\overline{h}_{v}\mid v\in V^{+}(T)\}$ in time $\mathcal{O}(|\hat{A}|)$ using 15. For given $x,y\in\mathbb{N}$ , let $\mathcal{T}_{v}$ be the time complexity required to query $H_{v}(x,y)$ , that is to return a routing from the set or to confirm that it is empty.

We will prove that

\mathcal{T}_{v}=\mathcal{O}\bigl{(}|\hat{A}(T_{v})|\log^{k_{v}-1}(|A(T_{v})|)% \bigr{)}.

(11)

Once we established this, for a given $x$ we can determine if there is some $r\in H_{t}(x,0)$ , that is an $s$ -directed compensated routing $r_{s}$ such that $\phi_{s}(r_{s})=x$ , within time $\mathcal{T}_{t}$ .

Moreover, by employing an exponential search using the approximation $\overline{h}_{t}(0)$ , we only need to check the non-emptiness of $H_{t}(x,0)$ for $\mathcal{O}(\log|A|)$ distinct values of $x$ . This process enables us to compute

\displaystyle h_{t}(0)

\displaystyle=\max\{\phi_{s}(r)\mid\hbox{$s$-directed compensated routing $r$}\}

in time $\mathcal{O}(\mathcal{T}_{t}\log|A|)=\mathcal{O}\bigl{(}|\hat{A}|\log^{k}(|A|)% \bigr{)}$ , which completes the proof.

So it remains to prove (11). To do so, we first establish the following claim.

Claim 18.

For $v\in V^{+}(T)$ and any choice of $u^{*}\in N^{-}_{s}\!(v)$ , it holds that

\displaystyle\mathcal{T}_{v}=\mathcal{O}\Bigl{(}|\hat{A}^{+}(v)|+\mathcal{T}_{% u^{*}}+\sum_{u\in N^{-}_{s}\!(v)\setminus\{u^{*}\}}\mathcal{T}_{u}\log|A(T_{u}% )|\Bigr{)}\enspace.

Proof.

Given $x,y\in\mathbb{N}$ , our objective is to either find a routing $r\in H_{v}(x,y)$ or confirm that the set is empty. We may assume $x>0$ as otherwise we simply return $r=\bm{0}$ .

For each $u\in N^{-}_{s}(v)$ , let $y_{u}=q^{v}_{u}(x)$ .

First, we determine $r(v)=q_{v}(x)$ . Then, for each $u\in N^{-}_{s}\!(v)\setminus\{u^{*}\}$ , we determine $\overline{h}_{u}(y_{u})$ .

Using the induced bound of that approximation on $h_{u}(y_{u})$ , we perform an exponential search to obtain $x_{u}=h_{u}(y_{u})$ and $r_{u}\in H_{u}(x_{u},y_{u})$ .

To perform this, due to 15, we require at most $1+\log|A(T_{u})|$ queries to $H_{u}$ . As for $x_{u^{*}}$ , we set

\displaystyle z=r(v)-\sigma(v)-y-\sum_{u\in N^{-}_{s}\!(v)\setminus\{u^{*}\}}x% _{u}\enspace.

If $z\leq 0$ , we let $x_{u^{*}}=0$ and $r_{u^{*}}$ be the zero routing which belongs to $H_{u^{*}}(0,y_{u^{*}})$ . Otherwise, we let $x_{u^{*}}=z$ and query $r_{u^{*}}\in H_{u^{*}}(x_{u^{*}},y_{u^{*}})$ . If no such $r_{u^{*}}$ exists, we terminate and assert $H_{v}(x,y)=\emptyset$ .

Finally, we return $r$ as given by $r(v)$ and whose restrictions to $V(T_{u})$ is given by $r_{u}$ for every $u\in N^{-}_{s}\!(v)$ .

Now, the procedure takes the claimed time if $r(v)$ and $\{y_{u}\mid u\in N^{-}_{s}\!(v)\}$ can be calculated in time $\mathcal{O}(|\hat{A}^{+}(v)|)$ . This can be done using a straightforward procedure employing two Euclidean divisions and two iterations through the encoding $\hat{A}^{+}(v)$ .

As for correctness, if we failed to obtain $r_{u^{*}}$ , we must have $x_{u^{*}}>h_{u^{*}}(y_{u^{*}})$ . Hence:

\displaystyle 0

\displaystyle>r(v)-\sigma(v)-y-\sum_{u\in N^{-}_{s}(v)}h_{u}(y_{u}),

which by 11 implies $H_{v}(x,y)=\emptyset$ . Otherwise, $r$ satisfies every condition of 11 and thus $r\in H_{v}(x,y)$ . $\hfill\vartriangleleft$

To complete the proof of (11) we now proceed by induction. If $N^{-}_{s}(v)=\emptyset$ , we have $\mathcal{T}_{v}=\mathcal{O}(|\hat{A}^{+}(v)|)$ which satisfies the hypothesis as $k_{v}=1$ . Otherwise, by the induction hypothesis, for each $u\in N^{-}_{s}(v)$ , we have that $\mathcal{T}_{u}=\mathcal{O}\bigl{(}|\hat{A}(T_{u})|\log^{k_{u}-1}(|A(T_{u})|)% \bigr{)}$ .

Now, using 18, we obtain

\mathcal{T}_{v}=\mathcal{O}\Bigl{(}|\hat{A}^{+}(v)|+|\hat{A}(T_{u^{*}})|\log^{% k_{u^{*}}-1}(|A(T_{u^{*}})|)\\ +\sum_{u\in N^{-}_{s}(v)\setminus\{u^{*}\}}|\hat{A}(T_{u})|\log^{k_{u}}(|A(T_{% u})|)\Bigr{)}\enspace.

We choose $u^{*}\in N^{-}_{s}(v)$ such that $k_{u^{*}}=\max\{k_{u}\mid u\in N^{-}_{s}(v)\}$ . Then

\displaystyle k_{v}=\max\{k_{u^{*}}\}\cup\{k_{u}+1\mid u^{*}\neq u\in N^{-}_{s% }(v)\},

from which (11) follows. $\hfill\blacktriangleleft$

Proof of 1.

By 5, it suffices to show that Legal Multi-Arrival can be solved in the claimed time.

Our algorithm for 1 finds, for every $s\in S_{0}$ , an $s$ -directed compensated routing $r_{s}$ which maximizes $\phi_{s}(r)$ . This by Theorem 9 allows us to obtain the maximal legal routing $\hat{r}$ given by $\hat{r}(v)=\max\{r_{s}(v)\mid s\in S_{0}\}$ for $v\in V^{+}(T)$ .

Hence, for each $s\in S_{0}$ we need only show that $r_{s}$ can be obtained in time $\mathcal{O}\bigl{(}|\hat{A}|\log^{k}(|A|)\bigr{)}$ , which is established by 17.

If for some constant $C>0$ , we have $k\leq\frac{C\log|A|}{\log(\log|A|)}$ , then it is seen that $\log^{k}(|A|)\leq|A|^{C}$ , and thus the run time of the algorithm is $\mathcal{O}\Bigl{(}|A|^{\max(1,C)}\Bigr{)}$ .

Further, if for some constant $C>0$ , we have $k\leq C$ , by the fact that $\log(|A|)\leq|\hat{A}|$ , the run time is $\mathcal{O}\bigl{(}|\hat{A}|^{C+2}\bigr{)}$ . $\hfill\blacktriangleleft$

4.3 MULTI-ARRIVAL for Tree-like Simple Graphs

In this subsection, we focus on tree-like rotor graphs without parallel arcs, for which we prove that Multi-Arrival can be solved in polynomial time.

Theorem 2.

Multi-Arrival can be solved on tree-like rotor graphs $T$ with arc set $A$ , sink set $S_{0}$ and without parallel arcs in time $\mathcal{O}\bigl{(}|S_{0}||A|^{3}\bigr{)}$ . Furthermore, in the procedure, a full routing is obtained.

We now employ a dynamic program that given bounds $b_{1}\leq b_{2}$ that contain some unknown $s$ -directed compensated routing $r$ , constructs lower bounds of $\{h_{v}\mid v\in V^{+}(T)\}$ . Then, as $r$ is contained in those bounds, these lower bounds allow us to obtain an $s$ -directed compensated routing $r^{\prime}\geq r$ in time proportional to the size of these bounds.

Lemma 19.

Let $T$ be a tree-like rotor graph, and let $b_{1},b_{2}$ be two vectors such that there exists an $s$ -directed compensated routing $r$ with $b_{1}\leq r\leq b_{2}$ . Then we can construct an $s$ -directed compensated routing $r^{\prime}$ such that $r^{\prime}\geq r$ in time $\mathcal{O}(\Delta|\hat{A}|)$ where $\Delta=1+\max\big{\{}\phi^{v}_{w}(b_{2}(v))-\phi^{v}_{w}(b_{1}(v))\mid v\in V^% {+}(T)\text{ and }w=N^{+}_{s}(v)\big{\}}$ .

Proof.

First, we inductively construct for each $v\in V^{+}(T)$ a strictly increasing function $\hat{f}_{v}\colon I_{v}\to\mathbb{N}$ where $I_{v}=\{\phi^{v}_{w}(b_{1}(v)),\dots,\phi^{v}_{w}(b_{2}(v))\}$ and a function $\hat{h}_{v}\colon\mathbb{N}\to\mathbb{N}$ . The function $\hat{h}_{v}$ will serve as a lower bound for $h_{v}$ .

Suppose $\hat{h}_{u}$ has been constructed for each $u\in N^{-}_{s}(v)$ . We define $\hat{f}_{v}$ and $\hat{h}_{v}$ as follows:

	$\displaystyle\hat{f}_{v}(x)$	$\displaystyle=q_{v}(x)-\sigma(v)-\sum_{u\in N^{-}_{s}\!(v)}\hat{h}_{u}\bigl{(}% q^{v}_{u}(x)\bigr{)},\quad\hbox{for}\leavevmode\nobreak\ x\in I_{v},$
	$\displaystyle\hat{h}_{v}(y)$	$\displaystyle=\begin{cases}0&y<\min\hat{f}_{v},\\ \max\{x\in I_{v}\mid\hat{f}_{v}(x)\leq y\}&\min\hat{f}_{v}\leq y.\end{cases}$

It is clear that $\hat{f}_{v}$ is strictly increasing and $\hat{h}_{v}$ is an increasing function by arguments analogous to that of 12. Similarly, as by induction we have $\hat{h}_{u}\leq h_{u}$ for all $u\in N^{-}_{s}\!(v)$ , it follows that $\hat{h}_{v}\leq h_{v}$ .

Next, we will show that

\hat{h}_{v}\bigl{(}\phi^{w}_{v}(r(w))\bigr{)}\geq\phi^{v}_{w}(r(v))\enspace.

(12)

To this end, suppose that, by induction, $\hat{h}_{u}\bigl{(}\phi^{v}_{u}(r(v))\bigr{)}\geq\phi^{u}_{v}(r(u))$ for $u\in N^{-}_{s}\!(v)$ . Then as $r$ is a compensated routing, we have:

\displaystyle\phi^{w}_{v}(r(w))

\displaystyle\geq r(v)-\sigma(v)-\sum_{u\in N^{-}_{s}(v)}\phi^{u}_{v}(r(u))\enspace.

Since the function $\phi^{v}_{w}(\cdot)$ is increasing and $b_{1}(v)\leq r(v)\leq b_{2}(v)$ , we have $\phi^{v}_{w}(r(v))\in I_{v}$ . Also, $q_{v}(\phi^{v}_{w}(r(v)))=r(v)$ , as $r$ is $s$ -directed.

Consequently,

	$\displaystyle\hat{f}_{v}\bigl{(}\phi^{v}_{w}(r(v))\bigr{)}$	$\displaystyle=r(v)-\sigma(v)-\sum_{u\in N^{-}_{s}(v)}\hat{h}_{u}\bigl{(}\phi^{% v}_{u}(r(v))\bigr{)}$
		$\displaystyle\leq r(v)-\sigma(v)-\sum_{u\in N^{-}_{s}(v)}\phi^{u}_{v}(r(u))% \leq\phi^{w}_{v}(r(w))\enspace.$

From this, by the definition of $\hat{h}_{v}$ , (12) readily follows.

Next, we inductively construct an $s$ -directed routing $r^{\prime}$ and begin by setting $r^{\prime}(s)\!=\!r(s)\!=\!0$ .

We assume by induction that $r^{\prime}(w)$ is defined and satisfies $r^{\prime}(w)\geq r(w)$ .

Now, if $w\neq s$ and $r^{\prime}(w)=r(w)=0$ , we set $r^{\prime}(v)=0$ . From 11 we see that $r(v)=0$ . Otherwise, we define

r^{\prime}(v)=q_{v}\Bigl{(}\hat{h}_{v}\bigl{(}\phi^{w}_{v}(r^{\prime}(w))\bigr% {)}\Bigr{)}\enspace.

(13)

From $r^{\prime}(w)\geq r(w)$ and (12) it follows that $\hat{h}_{v}\bigl{(}\phi^{w}_{v}(r^{\prime}(w))\bigr{)}\geq\hat{h}_{v}\bigl{(}% \phi^{w}_{v}(r(w))\bigr{)}\geq\phi^{v}_{w}(r(v))$ .

Taking $q_{v}$ from the left and right sides of this inequality, we get $r^{\prime}(v)\geq r(v)$ .

Since $r^{\prime}\geq r$ , it remains to show that $r^{\prime}$ is $s$ -directed and compensated. We accomplish this by showing that the conditions of 11 are satisfied by $r^{\prime}$ . Let $v\in V^{+}(T)$ and assume for each $u\in N^{-}_{s}(v)$ we have $r^{\prime}_{u}\in H_{u}\bigl{(}\phi^{u}_{v}(r^{\prime}(u)),\phi^{v}_{u}(r^{% \prime}(v))\bigr{)}$ where $r^{\prime}_{u}$ denotes the restriction of $r^{\prime}$ to $T_{u}$ . We will show that $r^{\prime}_{v}$ belongs to $H_{v}\bigl{(}\phi^{v}_{w}(r^{\prime}(v)),\phi^{w}_{v}(r^{\prime}(w))\bigr{)}$ . By construction, $\phi^{v}_{w}(r^{\prime}(v))>0$ if and only if $r^{\prime}_{v}(v)>0$ . The case $r^{\prime}_{v}(v)=0$ is trivial as then we see that $r^{\prime}_{v}=\bm{0}$ . Otherwise, we need to show that (1)–(3) of 11 hold. By the assumption, (3) is already satisfied.

Taking $\phi^{v}_{w}(\cdot)$ from the both sides of (13), we obtain $\phi^{v}_{w}(r^{\prime}(v))=\hat{h}_{v}\bigl{(}\phi^{w}_{v}(r^{\prime}(w))% \bigr{)}$ . So $r^{\prime}(v)$ satisfies (1).

Finally, by definition of $\hat{h}_{v}$ and $r^{\prime}$ , we have:

	$\displaystyle\phi^{w}_{v}(r^{\prime}(w))$	$\displaystyle\geq\hat{f}_{v}\bigl{(}\phi^{v}_{w}(r^{\prime}(v))\bigr{)}$
		$\displaystyle=r^{\prime}(v)-\sigma(v)-\sum_{u\in N^{-}_{s}(v)}\hat{h}_{u}\bigl% {(}\phi^{v}_{u}(r^{\prime}(v))\bigr{)}=r^{\prime}(v)-\sigma(v)-\sum_{u\in N^{-% }_{s}(v)}\phi^{u}_{v}(r^{\prime}(u))\enspace.$

Consequently, (2) holds as well.

Hence, the procedure returns the desired $s$ -directed compensated routing $r^{\prime}\geq r$ .

Note that $\hat{h}_{v}$ is increasing. Hence, it is straightforward to see that we can construct $\hat{h}_{v}$ by iterating through $x\in\{\phi^{v}_{w}(b_{1}(v)),\dots,\phi^{v}_{w}(b_{2}(v))\}$ while keeping track of the index $x_{u}$ for each $u\in N^{-}_{s}(v)$ that corresponds to the maximal $\hat{f}_{u}(x_{u})\leq\phi^{v}_{u}(q_{v}(x))$ . Hence, we can construct $\hat{h}_{v}$ in time $\mathcal{O}\bigl{(}|\hat{A}^{+}(v)|\Delta+|N^{-}_{s}(v)|\Delta\bigr{)}$ . In total, including the construction of $r^{\prime}$ , we thus take time at most $\mathcal{O}(\Delta|\hat{A}|)$ . $\hfill\blacktriangleleft$

Proof of 2.

We proceed analogously to the proof of 1. It suffices to show how to obtain $r_{s}$ for each sink $s\in S_{0}$ .

We will demonstrate that for the simple tree-like rotor graph $T$ , we can obtain bounds $b_{1}\leq b_{2}$ in time $\mathcal{O}(|A|)$ , which contain an $s$ -directed compensated routing $r$ which maximizes $\phi_{s}(r)$ . Additionally, we show that the parameter $\Delta$ , defined as in 19, satisfies $\Delta\leq\mathcal{O}(|A|^{2})$ . We then plug these into 19, which allows us to construct the desired routing $r_{s}$ in time $\mathcal{O}(|A|^{3})$ . Note that, since $T$ is simple, we have $|\hat{A}|=\mathcal{O}(|A|)$ . The remainder of the proof is therefore devoted to finding the required vectors $b_{1}$ and $b_{2}$ .

Let $\{t\}=N^{-}_{s}(s)$ and let $r$ denote the component-wise maximal routing in $H_{t}(h_{t}(0),0)$ . We first construct, for each $v\in V^{+}(T)$ , the affine approximations $\overline{h}_{v}$ given in 15. To this end, define $b_{1}(s)=b_{2}(s)=0$ . Now, for $v\in V^{+}(T)$ and $w=N^{+}_{s}(v)$ , assume we have constructed $b_{1}(w)\leq r(w)\leq b_{2}(w)$ . Hence:

\displaystyle h_{v}\bigl{(}\phi^{w}_{v}(b_{1}(w))\bigr{)}\leq h_{v}\bigl{(}% \phi^{w}_{v}(r(w))\bigr{)}\leq h_{v}\bigl{(}\phi^{w}_{v}(b_{2}(w))\bigr{)}\enspace.

Since $r$ is maximal we have that $\phi^{v}_{w}(r(v))=h_{v}\bigl{(}\phi^{w}_{v}(r(w))\bigr{)}$ . From $r$ being $s$ -directed it follows that

\displaystyle q_{v}\bigl{(}h_{v}(\phi^{w}_{v}(b_{1}(w)))\bigr{)}\leq r(v)\leq q% _{v}\bigl{(}h_{v}(\phi^{w}_{v}(b_{2}(w)))\bigr{)}\enspace.

Hence, using $\overline{h}_{v}$ with $C_{v}=2|A(T_{v})|$ denoting a bound on the error, we define:

\displaystyle b_{1}(v)=q_{v}\Bigl{(}\overline{h}_{v}\bigl{(}\phi^{w}_{v}(b_{1}% (w))\bigr{)}-C_{v}\Bigr{)}\leq r(v)\leq q_{v}\Bigl{(}\overline{h}_{v}\bigl{(}% \phi^{w}_{v}(b_{2}(w))\bigr{)}+C_{v}\Bigr{)}=b_{2}(v)\enspace.

Our next task, is to show that for each $v\in V^{+}(T)$ , it holds that

|b_{1}(v)-b_{2}(v)|\leq 4d_{+}(v)|A|\operatorname{dist}(s,v)\enspace.

(14)

We prove this relation by induction starting at $t$ . The base case is trivial, as

\displaystyle|b_{1}(t)-b_{2}(t)|

\displaystyle=\left|q_{t}\Bigl{(}\overline{h}_{t}\bigl{(}0\bigr{)}-C_{t}\Bigr{% )}-q_{t}\Bigl{(}\overline{h}_{t}\bigl{(}0\bigr{)}+C_{t}\Bigr{)}\right|\leq 4d_% {+}(t)|A|\enspace.

Assume that (14) holds for $v$ ; we now prove it for $u\in N^{-}_{s}(v)$ . Since $T$ is simple, we have that $q_{u}(x)-q_{u}(x^{\prime})=d_{+}(u)(x-x^{\prime})$ and

\displaystyle\left|\phi^{v}_{u}(x)-\phi^{v}_{u}(x^{\prime})\right|

\displaystyle\leq\left\lceil\frac{|x-x^{\prime}|}{d_{+}(v)}\right\rceil.

Furthermore, as $\overline{h}_{v}$ is a contraction (see (9)), we obtain:

	$\displaystyle\|b_{1}(u)-b_{2}(u)\|$	$\displaystyle=d_{+}(u)\Bigl{(}\left\|\overline{h}_{v}(\phi^{v}_{u}(b_{1}(v)))-% \overline{h}_{v}(\phi^{v}_{u}(b_{2}(v)))\right\|+2C_{u}\Bigr{)}$
		$\displaystyle\leq d_{+}(u)\Bigl{(}\left\|\phi^{v}_{u}(b_{1}(v))-\phi^{v}_{u}(b_% {2}(v))\right\|+2C_{u}\Bigr{)}$
		$\displaystyle\leq d_{+}(u)\left(\frac{\|b_{1}(v)-b_{2}(v)\|}{\|d_{+}(v)\|}+2C_{u}+% 1\right)$
		$\displaystyle\leq 4d_{+}(u)\left(\operatorname{dist}(s,v)\|A\|+\|A(T_{u})\|+1% \right)\leq 4d_{+}(u)\operatorname{dist}(s,u)\|A\|\enspace.$

By (14) it holds that for each $v\in V^{+}(T)$ , $\left|\phi^{v}_{w}(b_{1}(v))-\phi^{v}_{w}(b_{2}(v))\right|=\mathcal{O}(|A|^{2})$ , implying that the error $\Delta$ , defined as in 19, satisfies $\Delta\leq\mathcal{O}(|A|^{2})$ . This completes the proof. $\hfill\blacktriangleleft$

5 Conclusion

Our main result is a quasi-polynomial time algorithm for Multi-Arrival on tree-like multigraphs. We established the polynomial-time solvability of Multi-Arrival on path-like multigraphs, and on tree-like multigraphs with bounded contracted height. Thereby, we extended the polynomial-time algorithm by Auger et al., which was restricted to path-like rotor graphs with certain uniform rotor order, to a much wider class of instances.

The notion of contracted height, as we introduce it in this paper, is related to several other classic notions of height on trees, such as topological height. Nonetheless, we have not found any direct reference of this concept in the literature. It may therefore be interesting to explore its relationship to those well-known concepts of height further.

The complexity of Arrival in general graphs remains widely open. As a next step, it could be valuable to improve the quasi-polynomial time algorithms for Multi-Arrival on tree-like rotor graphs to a polynomial-time algorithm.

References

[1] David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial time algorithm for ARRIVAL on tree-like multigraphs. In Proc. MFCS 2022, volume 241 of Leibniz Int. Proc. Inform., pages Art. No. 12, 14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.MFCS.2022.12.
[2] David Auger, Pierre Coucheney, Loric Duhazé, and Kossi Roland Etse. Generalized ARRIVAL problem for rotor walks in path multigraphs. In Proc. Reachability problems 2023, volume 14235 of Lecture Notes Comput. Sci., pages 183–198. Springer, 2023. doi:10.1007/978-3-031-45286-4_14.
[3] Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, and Emo Welzl. ARRIVAL: a zero-player graph game in $\mathsf{NP}\cap\mathsf{coNP}$ . In A journey through discrete mathematics, pages 367–374. Springer, Cham, 2017. doi:10.1007/978-3-319-44479-6_14.
[4] John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability switching games. Log. Methods Comput. Sci., 17(2):Paper No. 10, 29, 2021. doi:10.23638/LMCS-17(2:10)2021.
[5] Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: Next Stop in CLS. In Proc. ICALP 2018, volume 107 of Leibniz Int. Proc. Informatics, pages 60:1–60:13, 2018. doi:10.4230/LIPICS.ICALP.2018.60.
[6] Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A subexponential algorithm for ARRIVAL. In Proc. ICALP 2021, volume 198 of Leibniz Int. Proc. Inform., pages 69:1–69:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.69.
[7] Giuliano Pezzolo Giacaglia, Lionel Levine, James Propp, and Linda Zayas-Palmer. Local-to-global principles for the hitting sequence of a rotor walk. Electron. J. Combin., 19(1):Paper 5, 23, 2012. doi:10.37236/12.
[8] Phuc Hung Hoang. On Two Combinatorial Reconfiguration Problems: Reachability and Hamiltonicity. PhD thesis, ETH Zurich, 2022.
[9] Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson. Chip-firing and rotor-routing on directed graphs. In In and out of equilibrium. 2, volume 60 of Progr. Probab., pages 331–364. Birkhäuser, Basel, 2008. doi:10.1007/978-3-7643-8786-0_17.
[10] Vyatcheslav B. Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Phys. Rev. Lett., 77(25):5079, 1996. doi:10.1103/PhysRevLett.77.5079.
[11] Lilla Tóthmérész. Rotor-routing reachability is easy, chip-firing reachability is hard. European J. Combin., 101:Paper No. 103466, 9, 2022. doi:10.1016/j.ejc.2021.103466.

[bib.bib1] [1] David Auger, Pierre Coucheney, and Loric Duhazé. Polynomial time algorithm for ARRIVAL on tree-like multigraphs. In Proc. MFCS 2022, volume 241 of Leibniz Int. Proc. Inform., pages Art. No. 12, 14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.MFCS.2022.12.

[bib.bib2] [2] David Auger, Pierre Coucheney, Loric Duhazé, and Kossi Roland Etse. Generalized ARRIVAL problem for rotor walks in path multigraphs. In Proc. Reachability problems 2023, volume 14235 of Lecture Notes Comput. Sci., pages 183–198. Springer, 2023. doi:10.1007/978-3-031-45286-4_14.

[bib.bib3] [3] Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, and Emo Welzl. ARRIVAL: a zero-player graph game in $\mathsf{NP}\cap\mathsf{coNP}$ . In A journey through discrete mathematics, pages 367–374. Springer, Cham, 2017. doi:10.1007/978-3-319-44479-6_14.

[bib.bib4] [4] John Fearnley, Martin Gairing, Matthias Mnich, and Rahul Savani. Reachability switching games. Log. Methods Comput. Sci., 17(2):Paper No. 10, 29, 2021. doi:10.23638/LMCS-17(2:10)2021.

[bib.bib5] [5] Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová. ARRIVAL: Next Stop in CLS. In Proc. ICALP 2018, volume 107 of Leibniz Int. Proc. Informatics, pages 60:1–60:13, 2018. doi:10.4230/LIPICS.ICALP.2018.60.

[bib.bib6] [6] Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang. A subexponential algorithm for ARRIVAL. In Proc. ICALP 2021, volume 198 of Leibniz Int. Proc. Inform., pages 69:1–69:14. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021. doi:10.4230/LIPIcs.ICALP.2021.69.

[bib.bib7] [7] Giuliano Pezzolo Giacaglia, Lionel Levine, James Propp, and Linda Zayas-Palmer. Local-to-global principles for the hitting sequence of a rotor walk. Electron. J. Combin., 19(1):Paper 5, 23, 2012. doi:10.37236/12.

[bib.bib8] [8] Phuc Hung Hoang. On Two Combinatorial Reconfiguration Problems: Reachability and Hamiltonicity. PhD thesis, ETH Zurich, 2022.

[bib.bib9] [9] Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuval Peres, James Propp, and David B. Wilson. Chip-firing and rotor-routing on directed graphs. In In and out of equilibrium. 2, volume 60 of Progr. Probab., pages 331–364. Birkhäuser, Basel, 2008. doi:10.1007/978-3-7643-8786-0_17.

[bib.bib10] [10] Vyatcheslav B. Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Phys. Rev. Lett., 77(25):5079, 1996. doi:10.1103/PhysRevLett.77.5079.

[bib.bib11] [11] Lilla Tóthmérész. Rotor-routing reachability is easy, chip-firing reachability is hard. European J. Combin., 101:Paper No. 103466, 9, 2022. doi:10.1016/j.ejc.2021.103466.

	$\displaystyle\left\|q_{v}(x)-\overline{q}_{v}(x)\right\|$	$\displaystyle=\left\|\bigl{(}q_{v}(d(v,w)+t)-q_{v}(d(v,w))\bigr{)}-\frac{td_{+}% (v)}{d(v,w)}\right\|<d_{+}(v),$		(6)
	$\displaystyle\left\|q^{v}_{u}(x)-\overline{q}^{v}_{u}(x)\right\|$	$\displaystyle=\left\|\bigl{(}q^{v}_{u}(d(v,w)+t)-q^{v}_{u}(d(v,w))\bigr{)}-% \frac{td(v,u)}{d(v,w)}\right\|<d(v,w)\enspace.$		(7)

	$\displaystyle\|b_{1}(u)-b_{2}(u)\|$	$\displaystyle=d_{+}(u)\Bigl{(}\left\|\overline{h}_{v}(\phi^{v}_{u}(b_{1}(v)))-% \overline{h}_{v}(\phi^{v}_{u}(b_{2}(v)))\right\|+2C_{u}\Bigr{)}$
		$\displaystyle\leq d_{+}(u)\Bigl{(}\left\|\phi^{v}_{u}(b_{1}(v))-\phi^{v}_{u}(b_% {2}(v))\right\|+2C_{u}\Bigr{)}$
		$\displaystyle\leq d_{+}(u)\left(\frac{\|b_{1}(v)-b_{2}(v)\|}{\|d_{+}(v)\|}+2C_{u}+% 1\right)$
		$\displaystyle\leq 4d_{+}(u)\left(\operatorname{dist}(s,v)\|A\|+\|A(T_{u})\|+1% \right)\leq 4d_{+}(u)\operatorname{dist}(s,u)\|A\|\enspace.$

A Quasi-Polynomial Time Algorithm for Multi-Arrival on Tree-Like Multigraphs

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Funding:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Our Contributions.

Theorem 1 (Informal).

Theorem 2 (Informal).

2 Preliminaries

2.1 Directed Multigraphs

2.2 Rotor-Routing

2.3 Arrival and Rotor-Routing Games

Lemma 3 ([9, Lemma 3.9]).

Problem (Arrival [3]).

Problem (Legal Multi-Arrival [8]).

Proposition 4 ([1, Theorem 2]).

Problem (Multi-Arrival [1]).

Proposition 5.

Proof.

Claim.

Proof.

3 Routing Decompositions

3.1 Destination Graphs

3.2 Compensated Routings

Proposition 6.

Proof.

3.3 𝒔-Directed Routings

Lemma 7.

Proof.

Lemma 8.

Proof.

Theorem 9.

Proof.

4 Algorithms for Multi-Arrival on Tree-Like Rotor Graphs

4.1 Relative Rotor Subgraphs

Lemma 10.

Proof.

Lemma 11.

Proof.

Lemma 12.

Proof.

4.2 MULTI-ARRIVAL for Tree-Like Multigraphs

Lemma 13.

Proof.

Theorem 1.

Corollary 14.

Lemma 15.

Proof.

Claim.

Proof.

Claim 16.

Proof.

Lemma 17.

Proof.

Claim 18.

Proof.

Proof of 1.

4.3 MULTI-ARRIVAL for Tree-like Simple Graphs

Theorem 2.

Lemma 19.

Proof.

Proof of 2.

5 Conclusion

References

3.3 $𝒔$ -Directed Routings