DAVID Lab.,UVSQ, Université Paris Saclay, 45 avenue des Etats-
Unis,78000,Versailles, France and https://www.david.uvsq.fr/?profile=auger-
david david.auger@uvsq.frhttps://orcid.org/0000-0003-1886-1901 DAVID
Lab.,UVSQ, Université Paris Saclay, 45 avenue des Etats-Unis,78000,Versailles,
France and https://www.david.uvsq.fr/?profile=coucheney-pierre-2
<EMAIL_ADDRESS>DAVID Lab.,UVSQ, Université Paris Saclay, 45 avenue
des Etats-Unis,78000,Versailles, France and LISN,Université Paris Saclay,
France and https://www.lri.fr/membre_en.php?mb=2713
loric.duhaze@uvsq.frhttps://orcid.org/my-orcid?orcid=0000-0002-9898-5631This
research was partially supported by Labex DigiCosme
(project ANR11LABEX0045DIGICOSME) operated by ANR as part of the program "
Investissement d’Avenir " Idex ParisSaclay (ANR11IDEX000302). David Auger,
Pierre Coucheney and Loric Duhazé <ccs2012> <concept>
<concept_id>10002950</concept_id> <concept_desc>Mathematics of
computing</concept_desc> <concept_significance>500</concept_significance>
</concept> </ccs2012> [500]Mathematics of computing

###### Acknowledgements.

We want to thank Johanne Cohen for her advises and attentive review.John Q.
Open and Joan R. Access 2 42nd Conference on Very Important Topics (CVIT 2016)
CVIT 2016 CVIT 2016 December 24–27, 2016 Little Whinging, United Kingdom 42 23

# Polynomial Time Algorithm for ARRIVAL on Tree-like Multigraphs

David Auger  Pierre Coucheney  Loric Duhazé

###### Abstract

A _rotor walk_ in a directed graph can be thought of as a deterministic
version of a Markov Chain, where a pebble moves from vertex to vertex
following a simple rule until a terminal vertex, or sink, has been reached.
The _ARRIVAL problem_ , as defined by Dohrau and al. [7], consists in
determining which sink will be reached. While the walk itself can take an
exponential number of steps, this problem belongs to the complexity class NP
$\cap$ co-NP without being known to be in P. Several variants have been
studied where we add one or two players to the model, defining deterministic
analogs of stochastic models (e.g., Markovian decision processes, Stochastic
Games) with rotor-routing rules instead of random transitions. The
corresponding decision problem addresses the existence of strategies for
players that ensures some condition on the reached sink. These problems are
known to be $NP$-complete for one player and $PSPACE$-complete for two
players. In this work, we define a class of directed graphs, namely _tree-like
multigraphs_ , which are multigraphs having the global shape of an undirected
tree. We prove that in this class, ARRIVAL and its different variants can be
solved in linear time, while the number of steps of rotor walks can still be
exponential. To achieve this, we define a notion of _return flow_ , which
counts the number of times the pebble will bounce back in subtrees of the
graph.

###### keywords:

Rotor-routing, Rotor Walk, Reachability Problem, Game Theory, Tree-like
Multigraph

##  1 Introduction

The _rotor routing_ , or _rotor walk model_ , has been studied under different
names: _eulerian walkers_ [17, 16] and _patrolling algorithm_ [19]. It shares
many properties with a more algebraic focused model: _abelian sandpiles_ [3,
14]. We can cite [11] and [14] as general introductions to this cellular
automaton.

Let us explain briefly how a rotor walk works. Consider a directed graph and
for each vertex $v$, if $v$ has $k$ outgoing arcs, number these arcs from $1$
to $k$. Then, we place a pebble on a starting vertex and proceed to the walk.
On the initial vertex, the pebble moves to the next vertex according to arc
$1$. It does the same on the second vertex and so on. But the second time that
a vertex is reached, the pebble will move according to arc $2$, and so on
until arc $k$ has been used, and then we start again with arc $1$.

This elementary rule defines the rotor routing which has many interesting
properties. In particular, it is easily shown that if it the graph is
connected enough, the pebble will explore all vertices, but the time needed
for such an exploration can be exponential in the number of vertices.

In this work, we fix a set of vertices that we call sinks and stop the walking
process when a sink is reached. The problem of determining, for a starting
configuration (numbering) of arcs and an initial vertex, which sink will be
reached first is the ARRIVAL problem. It is defined in [7] together with a
proof that the problem belongs to the complexity class NP $\cap$ co-NP, but it
is not known to be in P. It has then been shown in [9] that the problem is in
the smaller complexity class UP $\cap$ co-UP, and a subexponential algorithm
has been proposed in [10], based on computing a Tarski fixed point. This
algorithm is even polynomial if the graph is almost acyclic (in a certain
sense).

A direct application of the rotor-routing automaton is that several structural
properties of Markov chains can be approximated or bounded by rotor walks see
[5, 6, 8]. It seems natural to extend these results to decisional variants and
define rotor analogs for _Markov decision processes_ and _stochastic games_
[18]. It is proved in [18] that deciding if a player can ensure some value is
NP-complete for the one-player version and PSPACE-complete for the two-player
version.

##### Contributions and Organization of the Paper

In this work, we define the class _tree-like multigraphs_ , where the number
of steps needed to complete a rotor walk can still be exponential, but where
the tree-like structure helps to efficiently solve ARRIVAL, as well as its one
and two players variants, in linear time. It is to be noted that tree-like
multigraphs are not almost acyclic in the sense of [10], thus their algorithm
does not run in polynomial time in our case.

In section 2, we first give some standard definitions for multigraphs and
proceed to define rotor walks in this context together with different rotor-
routing notions (_exit pattern, cycle pushing_ , etc.). We begin our study of
ARRIVAL by a particular graph, the _Path Graph_ , in section 3 and introduce
the main tool that we use, namely the _return flow_. Next, we define tree-like
multigraphs and return flow in the general case in section 4.

The ARRIVAL problem (with zero player) is solved by an almost linear algorithm
which is detailed in section 5. Then we proceed to the case of one-player
rotor games and two-player rotor games respectively in section 6 and section
7.

Finally, in section 8 we study and improve the complexity of solving ARRIVAL
and the associated decision problems in the particular case of simple graphs
_i.e._ graphs that admit a unique arc for each couple of adjacent vertices.

The following table summarizes our results (bold), i.e. time complexity of
computing the sink (or the optimal sink, for one-player and two-player)
reached by a particle starting on a particular vertex in a graph $G=(V,A)$.
The first column states the complexity of the natural algorithm to solve these
problems, namely simulating the _rotor walk_.

Rotor Walk 0 player 1 player 2 players General digraph _exponential_ NP $\cap$
coNP NP-complete PSPACE-complete Tree-like multigraph exponential
$\bm{O(|A|)}^{\textbf{\textdagger}}$ $\bm{O(|A|)}$ $\bm{O(|A|)}$ Simple Tree-
like multigraph $\bm{O(|V|^{2})}$ $\bm{O(|V|)}^{\textbf{\textdagger}}$
$\bm{O(|V|)}\textbf{*}$ $\bm{O(|V|)}\textbf{*}$

The ${\dagger}$ indicates the cases where we can solve the problem for all
vertices of the graph at the same time with this complexity. The * indicates
the cases where the problem can be solved for all vertices under certain
conditions.

##  2 Basic Definitions

###  2.1 Directed Multigraphs

In this paper, unless stated otherwise, we always consider a directed
multigraph $G=(V,{\cal A},h,t)$ where $V$ is a finite set of _vertices_ ,
${\cal A}$ is a finite set of _arcs_ , and $h$ (for _head_) and $t$ (for
_tail_) are two maps from ${\cal A}$ to $V$ defining incidence between arcs
and vertices. For a given arc $a\in{\cal A}$, vertex $h(a)$ is called the head
of $a$ and $t(a)$ is the tail of $a$. For sake of clarity, we only consider
graphs without arcs of the form $h(a)=t(a)$ (i.e. loops). All our complexity
results would remain true if we authorized them. Note that multigraphs can
have multiple arcs with the same head and tail. Let $u\in V$ be a vertex, we
denote by ${\cal A}^{+}(u)$ (resp. ${\cal A}^{-}(u)$) the subset of arcs
$a\in{\cal A}$ with tail $u$ (resp. with head $u$).

Let $\Gamma^{+}(u)$ (resp. $\Gamma^{-}(u)$) be the subset of vertices $v\in V$
such that there is an arc $a\in{\cal A}$ with $h(a)=v$ and $t(a)=u$
(resp.$h(a)=u$ and $t(a)=v$). A graph such that for all $u\in V$ we have
$|{\cal A}^{+}(u)|=|\Gamma^{+}(u)|$ is called _simple_. A vertex $u$ for which
$|\Gamma^{+}(u)\cup\Gamma^{-}(u)|=1$ is called a _leaf_.

###  2.2 Rotor Routing Mechanics

#### Rotor Graphs

Let $G=(V,{\cal A},h,t)$ be a multigraph.

######  Definition 2.1 (Rotor Order).

We define a _rotor order_ at $u\in V$ as an operator denoted by $\theta_{u}$
such that:

  * •

$\theta_{u}:{\cal A}^{+}(u)\rightarrow{\cal A}^{+}(u)$

  * •

for all $a\in{\cal A}^{+}(u)$, the orbit
$\\{a,\theta_{u}(a),\theta_{u}^{2}(a),...,\theta_{u}^{|{\cal
A}^{+}(u)|-1}(a)\\}$ of arc $a$ under $\theta_{u}$ is equal to ${\cal
A}^{+}(u)$, where $\theta_{u}^{k}(a)$ is the composition of $\theta_{u}$
applied to arc $a$ exactly $k$ times.

Observe that each arc of ${\cal A}^{+}(u)$ appears exactly once in any orbit
of $\theta_{u}$. Now, we will integrate the operator $\theta_{u}$ to our graph
structure as follows.

######  Definition 2.2 (Rotor Graph).

A _rotor graph_ $G$ consists in a (multi)graph $G=(V,{\cal A},h,t)$ together
with:

  * •

a partition $V=V_{0}\cup S_{0}$ of vertices, where $S_{0}\neq\emptyset$ is a
particular set of vertices called sinks, and $V_{0}$ is the rest of the
vertices;

  * •

a rotor order $\theta_{u}$ at each $u\in V_{0}$.

In this document, unless stated otherwise, all the graphs we consider are
rotor graphs with $G=(V_{0},S_{0},{\cal A},h,t,\theta)$.

######  Definition 2.3 (Rotor Configuration).

A _rotor configuration_ (or simply configuration) of a rotor graph $G$ is a
mapping $\rho$ from $V_{0}$ to ${\cal A}$ such that $\rho(u)\in{\cal
A}^{+}(u)$ for all $u\in V_{0}$. We denote by ${\cal C}(G)$ the set of all
rotor configurations on the rotor graph $G$.

What will be called a _particle_ in the remaining of this paper is a pebble
which will move from one vertex to another; hence the position of the particle
is characterized by a single vertex. This movement, called rotor walk, follows
specific rules that we detail after.

######  Definition 2.4 (Rotor-particle configuration).

A _rotor-particle configuration_ is a couple $(\rho,u)$ where $\rho$ is a
rotor configuration and $u\in V$ denotes the position of a particle.

#### Rotor Walk

######  Definition 2.5.

Let us define two mappings on ${\cal C}(G)\times V_{0}$ :

  * •

$\mathbf{turn}$ :

$\mathbf{turn}:{\cal C}(G)\times V_{0}\longrightarrow{\cal C}(G)$

is defined by

$\mathbf{turn}(\rho,u)=\rho^{\prime}$

where $\rho^{\prime}$ is equal to $\rho$ except at $v$ where
$\rho^{\prime}(u)=\theta_{u}(\rho(u))$.

  * •

_move_ :

$\mathbf{move}:{\cal C}(G)\times V_{0}\longrightarrow V$

is defined by

$\mathbf{move}(\rho,u)=h(\rho(u))$

By composing those mappings, we are now ready to define the _routing of a
particle_ which is a single step of a rotor walk.

######  Definition 2.6 (Routing of a Particle).

The routing of a particle from a rotor-particle configuration $(\rho,u)$ is a
mapping:

$\mathbf{routing}:{\cal C}(G)\times V_{0}\longrightarrow{\cal C}(G)\times V$

defined by

$\mathbf{routing}(\rho,u)=(\rho^{\prime},v)$

with $\rho^{\prime}=\mathbf{turn}(\rho,u)$ and $v=\mathbf{move}(\rho,u)$. This
can be viewed as the particle first travelling through $\rho(u)$ and then
$\rho(u)$ is replaced by $\theta_{u}(\rho(u))$. This operation is illustrated
in Figure 1.

######  Remark 2.7.

Our routing rule (move, then turn) is slightly different than the one defined
in [17] which is mostly used in the literature (turn, then move) but is more
convenient to study ARRIVAL. The two rules are equivalent up to applying
$\mathbf{turn}$ mapping on all vertices.

$u_{0}$$u_{1}$$u_{2}$$s_{1}$ $s_{2}$ 10102012

(a) Let $\rho$ be the rotor configuration depicted by the red arcs in dashes.

$u_{0}$$u_{1}$$u_{2}$$s_{1}$ $s_{2}$ 10102012

(b) The red rotor configuration in dashes is obtained by processing the
operation : $\mathbf{routing}(\rho,u_{2})$

Figure 1: A rotor-routing where the particle is depicted by a train and starts
on $u_{2}$. The sink-vertices are $s_{1}$ and $s_{2}$. The red arcs in dashes
represent the current rotor configuration. The rotor orders on the different
vertices are anticlockwise, i.e. they are:
$\theta_{u_{0}}$:($u_{0}$,$u_{2}$),($u_{0}$,$u_{1}$); $\theta_{u_{1}}$:
($u_{1}$,$u_{0}$),($u_{1}$,$u_{2}$),($u_{1}$,$s_{1}$); $\theta_{u_{2}}$:
($u_{2}$,$u_{1}$),($u_{2}$,$u_{0}$),($u_{2}$,$s_{2}$). These orders are also
depicted by the numbers around each vertex.

A rotor-routing is in fact a single step of a rotor walk.

######  Definition 2.8 (Rotor Walk).

A _rotor walk_ is a (finite or infinite) sequence of rotor-particle
configurations $(\rho_{i},u_{i})_{i\geq 0}$, which is recursively defined by
$(\rho_{i+1},u_{i+1})=\mathbf{routing}(\rho_{i},u_{i})$ as long as $u_{i}\in
V_{0}$.

One can check that the sequence of vertices in the rotor walk starting from
the rotor-particle configuration depicted on Figure 1(b) until a sink is
reached is $u_{1},u_{0},u_{2},u_{0},u_{1},u_{2},s_{2}$.

#### Routing to Sinks

Now that we have defined our version of rotor-walk, we proceed to the
corresponding version of the problem _ARRIVAL_. Indeed, _ARRIVAL_ was defined
in [7] using the traditional rotor routing operation where we turn first and
then move.

######  Definition 2.9 (Maximal Rotor Walk).

A maximal rotor walk is a rotor walk such that in the case where it is finite,
the last vertex must be a sink vertex $s\in S_{0}=V\setminus V_{0}$.

######  Definition 2.10 (Stopping Rotor Graph).

If, for any vertex $u\in V$, there exists a directed path from $u$ to a sink
$s\in S_{0}$, the graph is said to be _stopping_.

The next lemma is a classical result on rotor walks (cf Lemma 16 in [11]).

######  Lemma 2.11 (Finite number of steps).

If $G$ is stopping then any rotor walk in $G$ is finite.

######  Proof 2.12.

Given a rotor-particle configuration $(\rho,u)$ with $u\in V_{0}$, let $R$ be
a rotor walk starting from $(\rho,u)$. In this walk, a sink vertex of $S_{0}$
can only appear as the last vertex, hence it can be visited only once. Now,
let us consider $S_{1}=$ $\Gamma^{-}(S_{0})$. Each time a vertex $t\in S_{1}$
is visited, the particle moves to the next neighbour. Hence, it can be visited
at most $\lvert{\cal A}^{+}(t)\rvert$ times before a sink is reached and the
walk ends consequently. Now, let us consider the set $S_{2}=$
$\Gamma^{-}(S_{1})$, all vertices $u$ within $S_{2}$ can only be visited a
finite number of times, otherwise the particle will visit a vertex from
$S_{1}$ more than $\lvert{\cal A}^{+}(t)\rvert$ times. We proceed inductively
to show that all vertices can be visited only a finite number of times in $R$
since all vertices of $G$ have a directed path to a sink.

This proof provides a bound on the number of times an arc has been visited in
a finite rotor walk (4.11).

The main objective of our work is to study the sink that will be reached by a
maximal rotor walk from a rotor-particle configuration, if the rotor walk is
finite.

######  Definition 2.13 (Exit Sink).

Let $u\in V$, let $\rho$ be a configuration, if the maximal rotor walk
starting from $(\rho,u)$ is finite in $G$, then the sink reached by such a
rotor walk is denoted by $\mathbf{S}_{G}($$\rho$$,u)$ and called _exit sink_
of $u$ for the rotor configuration $\rho$ in $G$.

######  Definition 2.14 (Exit Pattern).

For a rotor configuration $\rho$ on a stopping rotor graph $G$, the _exit
pattern_ is the mapping that associates to each vertex $u\in V$, its exit sink
$\mathbf{S}_{G}($$\rho$$,u)$.

###  2.3 ARRIVAL and Complexity Issues

With our notations, ARRIVAL (see [7]) can be expressed as the following
decision problem:

In a stopping rotor graph $G$, given $(\rho,u)$ and $s\in S_{0}$ does
$\text{$\mathbf{S}_{G}($$\rho$$,u)$}=s$ ?

This problem belongs to NP $\cap$ co-NP for simple graphs as shown in [7], but
there is still no polynomial algorithm known to solve it. The case of eulerian
simple graphs can be solved in time O($|V+{\cal A}|^{3}$), since a finite
maximal rotor walk from $(\rho,v)$ ends in at most O($|V+{\cal A}|^{3}$)
routings (see [19]).

In the case of multigraphs, ARRIVAL still belongs to NP $\cap$ co-NP, since
the polynomial certificate used for simple graphs in [7] remains valid. Our
goal in this paper is to solve the problem in polynomial time for a particular
class of multigraphs. Despite that, even for a path multigraph, the routing
can be exponential, as shown on Figure 2.

$u_{n}$$u_{n-1}$$\dots$$u_{2}$$u_{1}$$u_{0}$$s$ Figure 2: Family of path-like
multigraphs where maximal routing can take an exponential number of steps in
the number of vertices, here equal to $n+2$. The interior vertices ($u_{0}$ to
$u_{n-1}$) have two arcs going left and one going right. Routing a particle
from $u_{0}$ to sink $s$ with the initial configuration $\rho$ drawn with red
arcs in dashes takes a non-polynomial time considering the anticlockwise rotor
ordering on each vertex, depicted by the curved arc in red.

In the example drawn in Figure 2, let us consider the number of times the
particle will travel from $u_{i}$ to $u_{i+1}$. Let $u_{0}$ be the starting
vertex: to reach the sink $s$, the particle needs to visit $u_{0}$ exactly
three times and so it will travel from $u_{0}$ to $u_{1}$ exactly two times.
Next, for $u_{1}$, each time the particle comes from $u_{0}$, it will travel
two times from $u_{1}$ to $u_{2}$ before visiting $u_{0}$ again. So the number
of times the particle travels from $u_{1}$ to $u_{2}$ is 4. One can check that
the number of times a particle starting from $u_{0}$ will travel from $u_{i}$
to $u_{i+1}$ before reaching $s$ is $2^{i+1}$.

###  2.4 Cycle Pushing

In order to speed-up the rotor walk process, a simple tool to avoid computing
every step of the walk is the use of _cycle pushing_. We keep the terminology
of _cycle pushing_ used in [11] – even if what is called a cycle in this
terminology is usually called a directed cycle or circuit in graph theory.

######  Definition 2.15 (Graph Induced by $\rho$).

If $G$ is a rotor multigraph and $\rho\in{\cal C}(G)$, we denote by
$G(\rho)=(V_{0},S_{0},\rho(V_{0}),h,t)$ the _graph induced_ by $\rho$ on $G$.
This means that $G(\rho)$ and $G$ have the same set of vertices, but $G(\rho)$
only contains arcs of $\rho(V_{0})$. In the following, we will say that the
(directed) cycle $C$ is _in_ $\rho$ if it belongs to $G(\rho)$.

######  Remark 2.16.

All non-sink vertices of $G(\rho)$ are of outdegree exactly one, hence a
vertex belongs to at most one cycle which is in $\rho$.

######  Definition 2.17 (Cycle $Pushing$).

Let $C=(u_{1},u_{2},u_{3},...,u_{k})$ be a directed cycle of $G(\rho)$. We
call _cycle push_ the operation on $\rho$ that leads to a configuration
$\rho^{\prime}$ such that:

  * •

for all $u_{i}\in C$, $\rho^{\prime}(u_{i})=\theta_{u_{i}}(\rho(u_{i}))$;

  * •

$\forall u\in V_{0}\setminus C,\rho^{\prime}(u)=\rho(u)$

i.e. we process a turn on all $u_{i}\in C$.

Note that a cycle push on a cycle $C$ can also be computed by putting a
particle on a vertex $u$ of $C$ and routing the particle until it comes back
to $u$ for the first time. Hence, cycle pushing is in a sense a shortcut on
the rotor walk process, so by a manner similar to 2.11 it follows that:

######  Lemma 2.18 (Finite Number of Cycle Pushes).

Given a stopping rotor graph, any sequence of cycle pushes is finite.

The previous result is well known in rotor walk studies ([14]). It implies
that, by processing a long enough sequence of successive cycle pushes, the
resulting configuration contains no directed cycles. Such a sequence of cycle
pushes is called _maximal_.

The two following results can be found in [11].

######  Lemma 2.19 (Exit Pattern conservation for Cycle Push).

If $G$ is a stopping rotor graph, for any rotor configuration $\rho$ and
configuration $\rho^{\prime}$ obtained from $\rho$ by a cycle push , the exit
pattern for $\rho$ and $\rho^{\prime}$ is the same.

######  Lemma 2.20 (Commutativity of Cycle Push).

In a stopping rotor graph, any sequence of cycle pushes starting from a given
rotor configuration $\rho$ leads to the same maximal, acyclic configuration
$\rho^{\prime}$ (i.e. $G(\rho^{\prime})$ is an acyclic graph).

######  Definition 2.21 (Destination Forest).

We call the configuration obtained by a maximal cycle push sequence on $\rho$
the _Destination Forest_ of $\rho$, denoted by $D(\rho)$.

The destination forest has a simple interpretation in terms of rotor walks:
start a rotor walk by putting a particle on any vertex of a stopping graph
$G$; consider a vertex $u\in V_{0}$; if the particle ever reaches $u$, it will
leave $u$ by arc $D(\rho)(u)$ on the last time it enters $u$.

In an acyclic configuration like $D(\rho)$, finding the exit pattern is very
simple, precisely:

######  Lemma 2.22 (Path to a sink).

If there is a directed path between $u\in V$ and $s\in S_{0}$ in $G(\rho)$
then $\text{$\mathbf{S}_{G}($$\rho$$,u)$}=s$. It follows that from $D(\rho)$
one can compute the exit pattern of $\rho$ in time complexity $O(|\cal{A}|)$.

This gives us a new approach, since computing the exit pattern of a
configuration $\rho$ can be done by computing its Destination Forest
$D(\rho)$. Note that by doing this we are solving a problem harder than
ARRIVAL because we compute the exit sink of all vertices simultaneously.

$u_{0}$$u_{1}$$u_{2}$$s_{1}$$s_{2}$ 10102012

(a) Red Rotor Configuration $\rho$ in dashes with rotor order on each vertex
described by increasing numbers.

$u_{0}$$u_{1}$$u_{2}$$s_{1}$$s_{2}$ 10102012

(b) The red configuration in dashes is obtained from a Cycle Push on the cycle
{($u_{0}$,$u_{2}$),($u_{2}$,$u_{1}$),($u_{1}$,$u_{0}$)}.

$u_{0}$$u_{1}$$u_{2}$$s_{1}$$s_{2}$ 10102012

(c) Destination Forest (depicted by red arcs in dashes) computed by two
successive cycle pushes on $\rho$.

Figure 3: Computation of the Destination Forest by successive cycle pushing.

######  Remark 2.23.

Pushing a cycle of length $k$ is a "shortcut" in a rotor walk as it allows to
do only one operation to simulate $k$ steps of the rotor walk. However, the
strategy consisting in pushing cycles until the Destination Forest is reached
(which is always the case if the graph is stopping) can still take an
exponential time. Indeed, let us consider Figure 2 again. As each cycle in
$G(\rho)$ is at most of size two, we are at most dividing by two the number of
steps used in the maximal rotor walk.

So, processing successive cycle pushes is not a suitable strategy to solve
ARRIVAL efficiently in general. However, the notion of equivalence classes
that we state below, which is useful for a deeper understanding of rotor
walks, is based on cycle pushing.

######  Definition 2.24 (Equivalence Class [11]).

We define an equivalence relation between configurations by considering that
two configurations $\rho_{1}$ and $\rho_{2}$ are in the same class if they
have the same Destination Forest.

The proof of the following theorem can be found in [11], Corollary 14. It
shows that equivalence of configurations is preserved by the routing of
particle to a sink.

######  Theorem 2.25.

Let $\rho_{1},\rho_{2}$ be two equivalent configurations. Let
$\rho^{\prime}_{1}$ and $\rho^{\prime}_{2}$ be the configurations obtained
respectively from $\rho_{1}$ and $\rho_{2}$ by routing a single particle from
the same vertex $u$ to a sink $s$. Then $\rho^{\prime}_{1}$ and
$\rho^{\prime}_{2}$ are equivalent.

##  3 The Simple Path Graph

In this section we give some results on a particular graph in order to give
intuition behind our following work on trees. The simple path graph on $n+2$
vertices is defined by $V=\\{s_{0},u_{1},u_{2},\dots,u_{n},s_{1}\\}$ and each
$u_{i}$ for $i\in\\{1,..,n\\}$ has an arc going to the vertex on the left and
another one going to the vertex on the right. Define then
$V_{0}=\\{u_{1},u_{2},...,u_{n}\\}$ together with $S_{0}=\\{s_{0},s_{1}\\}$.

See Figure 4 for the simple path graph with $n=4$.

In this section we will not only show that ARRIVAL can be solved in linear
time on simple path graphs but that we can solve a harder problem by
calculating the exit pattern for $\rho$ in linear time, i.e solving ARRIVAL
simultaneously for all vertices.

However, note that the maximum number of steps of a rotor walk (or a cycle
push sequence) in a simple path graph is not exponential but quadratic in $n$.
Indeed, one can check that the starting configuration that maximizes this
number of steps is the configuration where all arcs are directed towards the
central vertex $u_{\lceil n/2\rceil}$ (which is also the starting vertex in
the case of the rotor walk).

###  3.1 Routing One Particle on a Path Graph

It is an easy observation that the only elementary cycles in this graph are of
length 2, and that pushing such a cycle in a given configuration does not
change the global numbers of arcs respectively directed towards $s_{0}$ and
$s_{1}$ in the configuration. Hence the following definition:

######  Definition 3.1.

We say that a vertex $u_{i}\in V_{0}$ is _directed towards_ $s_{0}$ if
$h(\rho(u_{i}))\in\\{u_{i-1},s_{0}\\}$. Otherwise, $u_{i}$ is directed towards
$s_{1}$ (see 4(a)). We denote by $n_{1}(\rho)$ the number of vertices of
$V_{0}$ that are directed towards $s_{1}$.

From the observation above will follow that we can compute the exit pattern of
$\rho$ without having to process the sequence of cycle pushes, relying only on
the computation of $n_{1}(\rho)$.

######  Lemma 3.2 (Exit Sink Characterization).

Two configurations are equivalent if and only if they have the same number
$n_{1}$. In particular, for any configuration $\rho$, if $1\leq i\leq
n-n_{1}(\rho)$, then $\text{$\mathbf{S}_{G}($$\rho$$,u_{i})$}=s_{0}$,
otherwise $\text{$\mathbf{S}_{G}($$\rho$$,u_{i})$}=s_{1}$.

######  Proof 3.3.

A maximal cycle push sequence leads to an acyclic configuration, and we know
that $n_{1}$ is preserved by cycle push. Since there is a unique forest with
$n_{1}$ arcs directed towards $s_{1}$, namely the configuration where exactly
$u_{n-(n_{1}-1)},u_{n-(n_{1}-2)},\dots,u_{n}$ are directed towards $s_{1}$,
this is the Destination Forest (see 4(c)).

The previous lemma enables us to compute in linear time the exit pattern of
any configuration in a simple path graph – which easily solves ARRIVAL
simultaneously for all starting vertices.

$s_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$s_{1}$ (a) $u_{1}$ and $u_{2}$ are
directed towards $s_{1}$, and $u_{3}$ and $u_{4}$ are directed towards
$s_{0}$. Let $\rho$ be the initial configuration depicted here.

$s_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$s_{1}$ (b) Configuration obtained from
$\rho$ after a single cycle push on the cycle
$\\{(u_{2},u_{3});(u_{3},u_{2})\\}$. This configuration and $\rho$ are
equivalent since one is obtained from the other by cycle pushing so they have
the same Destination Forest. And as stated in 3.2 they have the same value
$n_{1}=2$.

$s_{0}$$u_{1}$$u_{2}$$u_{3}$$u_{4}$$s_{1}$ (c) Naturally, the Destination
Forest (i.e. rotor configuration after maximal cycle push sequence) of $\rho$
is equivalent to both previous configurations and the value $n_{1}$ remains
the same.

Figure 4: Illustration of 3.2 and its proof. The red arcs in dashes represent
the current rotor configuration.

###  3.2 Routing Several Particles

Here we present how the previous results can be used to solve ARRIVAL on a
simple path graph if we want to route multiple particles. We only study the
case of routing multiple particles in this case, the general case remaining an
open problem even for tree-like multigraphs.

It is well known that when we route any number of particles in a rotor graph,
the final configuration does not depend on the order in which the particles
move (which can alternate between particles) as long as we route the particles
to the sinks (see [14]).

######  Definition 3.4 (Equivalence Class for simple path graphs).

For $0\leq k\leq n$, let $C_{k}$ be the class of configurations $\rho$ with
$n_{1}(\rho)=k$ i.e. the set of configurations with exactly $k$ vertices
directed towards $s_{1}$.

Note that the equivalence classes defined just above are exactly the
equivalence classes of 2.24. We now explain the action of the movement of a
particle on these classes.

######  Theorem 3.5 (Group Action on simple path).

Consider a configuration $\rho\in C_{k}$ with $0\leq k\leq n$ and a vertex
$u_{i}$, $1\leq i\leq n$. Processing a maximal rotor walk from $(\rho,u_{i})$
leads to a configuration $\rho^{\prime}\in C_{j}$ where $j=(k+i)\mod n+1$.

######  Proof 3.6.

By Theorem 2.25 we can as well suppose that $\rho$ is acyclic, hence the $k$
vertices directed towards $s_{1}$ are exactly
$u_{n-k+1},u_{n-k+2},\dots,u_{n}$.

  * •

If $i\leq n-k$, then during the rotor walk, exactly $i$ vertices change
directions, hence $j=k+i$.

  * •

If $i>n-k$, then $n-i+1$ vertices change directions, hence
$j=k-(n-i+1)=k+i-(n+1)$.

When combining the action of multiple particles on classes, we obtain the
following theorem.

######  Theorem 3.7.

Let $\rho\in C_{k}$ be a rotor configuration. Consider the process where $m$
particles are routed to the sinks from initial positions
$i_{1},i_{2},\dots,i_{m}$ in any (alternating or not) order. Then:

  * •

The final configuration belongs to the class $C_{j}$ with

$j=k+i_{1}+i_{2}+\dots+i_{m}\mod n+1,$

  * •

exactly $p_{1}=\left\lfloor\dfrac{k+(\sum_{t=1}^{m}i_{t})}{n+1}\right\rfloor$
of these particles reach sink $s_{1}$, whereas $m-p_{1}$ reach $s_{0}$.

######  Proof 3.8.

By commutativity of the process, we can suppose that we fully route every
particle to a sink before proceeding to the next one. Consider
$\\{0,1,\dots,n\\}$ as a cycle of positions corresponding to the equivalence
classes. We start from position $k$ on the cycle, and every time a particle is
routed from its initial position $i_{t}$ to a sink, the final configuration
belongs to $C_{j}$ where $j$ is obtained by moving from $k$ on the cycle
$i_{t}$ times in cyclic ordering. It is contained in the proof of Theorem 3.5
that the particle ends in $s_{1}$ if and only if we move from position $n$ to
$0$ during this process. Hence, we just have to count the number of times this
will happen, which is simply the integer quotient of the final position
$k+i_{1}+\dots+i_{m}$ by the number of positions $n+1$.

Note that the previous theorem enables us to solve in linear time a variant of
ARRIVAL for multiple particles where we are interested in the number of
particles ending in each sink (even with an exponential number of particles,
if arithmetic computations are made in constant time).

###  3.3 The Return Flow with the Path Graph

The previous technique to compute the Destination Forest is based on an
invariance property of cycle pushes which is specific to the simple path
graph. It does not generalize directly to other graphs, which is why we now
give an equivalent formulation of the previous results. Instead of counting
the number of vertices that are directed toward sinks, we now consider the
number of vertices that are directed towards a given vertex $u$ on each side
of the path. To do this, we denote by $]u,u^{\prime}[$ the set of vertices
that lie between $u$ and $u^{\prime}$ in the order of vertices in the path,
excluding $u$ and $u^{\prime}$.

######  Definition 3.9.

Let $r_{1}(u)$ and $r_{0}(u)$ be the number of vertices that are respectively
directed towards $u$ in $]u,s_{1}[$ and $]s_{0},u[$.

We now restate 3.2 in terms of $r_{1}$ ans $r_{0}$.

######  Lemma 3.10.

For all non-sink vertices $u_{i}$, $\mathbf{S}_{G}($$\rho$$,u_{i})$$=s_{1}$ if
and only if

  * •

either $r_{1}(u_{i})<r_{0}(u_{i})$;

  * •

or $r_{1}(u_{i})=r_{0}(u_{i})$ and $u_{i}$ is directed towards $s_{1}$.

######  Proof 3.11.

We can decompose $n_{1}$ as follow:

$n_{1}=\underbrace{r_{0}(u_{i})}_{\text{vertices of
}]s_{0},u_{i}[}+\underbrace{I_{1}(u_{i})}_{\text{Orientation of
}u_{i}}+\underbrace{n-i-r_{1}(u_{i})}_{\text{vertices of }]u_{i},s_{1}[}$

where $I_{1}(u_{i})$ is 1 if $u_{i}$ is directed towards $s_{1}$ and $0$
otherwise.

Now, from 3.2 we know that
$\text{$\mathbf{S}_{G}($$\rho$$,u_{i})$}=s_{1}\Leftrightarrow i\geq
n-n_{1}+1$, which translates to

$r_{0}(u_{i})+I_{1}(u_{i})\geq r_{1}(u_{i})+1,$

hence the result.

######  Remark 3.12.

Consider the following process: on the simple path graph, we remove the arc
$(u_{i},u_{i-1})$ so that the particle cannot go from $u_{i}$ to
$[s_{0},u_{i}[$ anymore (in the case where $\rho(u_{i})=(u_{i},u_{i-1})$, we
change it to $\rho(u_{i})=(u_{i},u_{i+1})$). Now, we put a particle on $u_{i}$
and proceed to a maximal rotor walk. The number of times that the particle
travels through arc $(u_{i},u_{i+1})$ is exactly $r_{1}(u_{i})+1$. This
quantity is called the _return flow_ , which will be defined in the general
case in 4.8.

##  4 Tree-Like Multigraphs: Return Flow Definition

###  4.1 Tree-Like Multigraphs

To a directed multigraph $G=(V,{\cal A},h,t)$ we associate:

  * •

A simple directed graph $\hat{G}=(V,\hat{{\cal A}})$ such that, for $u,v\in V$
there is an arc from $u$ to $v$ in $\hat{G}$ if there is at least one arc
$a\in{\cal A}$ with $t(a)=u$ and $h(a)=v$. Please note that even if there are
multiple arcs $a$ that satisfy this property, there is only one arc with tail
$u$ and head $v$ in $\hat{{\cal A}}$. As it is unique, an arc from $u$ to $v$
in $\hat{{\cal A}}$ will simply be denoted by $(u,v)$.

  * •

A simple undirected graph $\overline{G}=(V,E)$ such that, for $u,v\in V$ there
is an edge between $u$ and $v$ in $\overline{G}$ if and only if there is at
least one arc $a\in{\cal A}$ such that $t(a)=u$ and $h(a)=v$ or $h(a)=u$ and
$t(a)=v$.

######  Definition 4.1 (Tree-Like Multigraph).

We say that a multigraph $G$ is _tree-like_ if $\overline{G}$ is a tree.

In this case, we define the leaves of $G$ as the leaves of $\overline{G}$.

######  Definition 4.2 (Tree-Like Rotor Multigraph).

A rotor multigraph $G=(V_{0},S_{0},{\cal A},h,t,\theta)$ is tree-like if
$(V,{\cal A},h,t)$ is tree-like, and its set of leaves contains $S_{0}$.

To avoid some complexity in the notation and proofs, we will only study
stopping tree-like rotor multigraphs. We first show that the general case can
be handled by reducing a non stopping instance to a stopping one.

######  Definition 4.3 (Sink Component).

A sink component is a strongly connected component in $G$ that does not
contain a sink vertex and such that there is no arc leaving the component.

Note that all sink components can be computed in linear time.

######  Lemma 4.4.

Consider a configuration $\rho$ on a (not necessarily stopping) tree-like
rotor multigraph $G=(V_{0},S_{0},{\cal A},h,t,\theta)$. Consider a
configuration $\rho^{\prime}$ on the _stopping_ tree-like rotor multigraph
$G^{\prime}=(V_{0}^{\prime},S_{0}^{\prime},{\cal A}^{\prime},h,t,\theta)$
where $G^{\prime}$ is obtained from $G$ by replacing each sink component by a
unique sink, and where $\rho^{\prime}(u)=\rho(u)$ for each $u\in
V_{0}^{\prime}$. For any $u\in V$, finding the exit sink of $u$ (if any) or
the sink component reached by $u$ in $G$ for the configuration $\rho$ can be
directly determined by solving ARRIVAL for the configuration $\rho^{\prime}$
in $G^{\prime}$.

######  Proof 4.5.

Let $\rho$ be a configuration in ${\cal C}(G)$ and $u\in V$ be a vertex.

  * •

If the particle enters a sink component $C$ while processing a rotor walk from
$(\rho,u)$ on $G$, then $u$ has no exit sink for $\rho$. The same rotor walk
in the graph $G^{\prime}$ ends in the sink that replaces $C$.

  * •

If the particle reaches a sink $s$ of $G$ while processing a maximal rotor
walk from $(\rho,u)$ on $G$, then it does not enter a sink component of $G$
hence the walk in $G^{\prime}$ is the same as in $G$.

Thanks to 4.4, we can work on graphs without sink components while keeping the
generality of our results. Note that, after replacing sink components by
sinks, the multigraph $G^{\prime}$ may no longer be a tree-like multigraph but
a forest-like multigraph. However we can split the study of ARRIVAL in each
tree-like component of this forest since a particle cannot travel between
those trees in a rotor walk.

###  4.2 Return Flows

Let us consider the simple example depicted on Figure 5 to motivate the
introduction of $(u,v)$-subtrees and return flows, which is our main tool.

$u$$v_{1}$$T_{1}$$v_{2}$$T_{2}$$v_{3}$$T_{3}$ Figure 5: We sketch a stopping
tree-like rotor multigraph as follows: a vertex $u$, its neighbours
$v_{1},v_{2},v_{3}$ (that might be sinks), respectively belonging to $T_{1}$,
$T_{2}$, $T_{3}$, the three connected components of $\bar{G}\setminus\\{u\\}$.
In particular, we have $\hat{{\cal
A}}^{+}(u)=\\{(u,v_{1});(u,v_{2});(u,v_{3})\\}$. We consider the rotor
configuration in red on $u$ and $\theta_{u}$ is the anticlockwise order on the
arcs of ${\cal A}^{+}(u)$. Consider the routing of a particle starting at $u$:
• the particle moves from $u$ to $v_{1}$, and stays for a while in the subtree
$T_{1}$ – where it either reaches a sink or comes back to $u$. Suppose it
comes back to $u$. Then: • the particle moves from $u$ to $v_{3}$, and either
reaches a sink in $T_{3}$ or comes back to $u$. Suppose it comes back to $u$
once again; • the rotor walk goes on, in $T_{3}$, then in
$T_{2},T_{1},T_{1},T_{3},\dots$ • until finally the particle ends in a sink in
one of the subtrees, say $T_{2}$. Now consider only the relative movement that
the particle had in $T_{2}$: it went from $u$ into $T_{2}$ and back to $u$ a
number of times, before it ended in a sink. If we were to replace $T_{1}$ and
$T_{3}$ by single arc leading back automatically to $u$, the relative movement
in $T_{2}$ would have been exactly the same. The return flow will be a
quantity that counts exactly the ability of each subtree to bounce back the
particle to $u$. During the process described above, every time the particle
enters a subtree and comes back to $u$, we can think of it as consuming a
single unit of return flow in this subtree. The first time that a particle
enters a subtree that has exactly one unit of return flow left, then the
particle must end in a sink of that subtree.

######  Definition 4.6 ($(u,v)$-subtree).

Let $(u,v)\in\hat{{\cal A}}$. The $(u,v)$-subtree $T_{(u,v)}$ is a
sub(multi)graph of $G$:

  * •

whose vertices are all the vertices of the connected component of
$\bar{G}\setminus\\{u\\}$ that contains $v$, together with $u$;

  * •

whose arcs are all the arcs of $G$ that link the vertices above, excepted in
$u$ where we remove all arcs of ${\cal A}^{+}(u)$ but a single arc $a$ with
head $v$. Such an arc $a$ always exists because $(u,v)\in\hat{{\cal A}}$;

  * •

whose rotor orders are unchanged except at $u$ where $\theta_{u}(a)=a$.

Such a subtree is a (not necessarily stopping) tree-like rotor multigraph. A
rotor configuration $\rho$ in $G$ can be thought of as a rotor configuration
$\rho^{\prime}$ in $T_{(u,v)}$ by defining that $\rho^{\prime}(u)=a$ and
$\rho^{\prime}(w)=\rho(w)$ for all $w\in T_{(u,v)}$.

We define a notion of _flow_ for a particular starting vertex.

######  Definition 4.7 (Flow of $(u,v)$).

We define the _flow_ on arc $(u,v)\in\hat{{\cal A}}$ for configuration $\rho$,
denoted by $F_{\rho}(u,v)$, the number of times (possibly infinite) that an
arc with tail $u$ and head $v$ is visited during the maximal rotor walk of a
particle starting from the rotor-particle configuration $(\rho,u)$. We denote
by $F_{\rho}(u)$ the flow vector of $(u,v)$ for every $v\in\Gamma^{+}(u)$.

######  Definition 4.8 (Return flow).

The _return flow_ of arc $(u,v)\in{\cal\hat{A}}$ for configuration $\rho$,
denoted by $r_{\rho}(u,v)$, is the flow on $(u,v)$ in the $(u,v)$-subtree
$T_{(u,v)}$.

Note that the return flow $r_{\rho}(u,v)$ also corresponds to the number of
times the particle visits $u$ while processing a maximal rotor walk from
$(\rho,u)$ in $T_{(u,v)}$ (see Figure 6). By definition of return flow, if
$u\in S_{0}$, then $r_{\rho}(u,v)=0$, and if $v\in S_{0}$, or if
$(v,u)\notin{\cal\hat{A}}$ then $r_{\rho}(u,v)=1$.

Remark also that, even if the tree-like multigraph is stopping, it is not
necessarily the case of any $(u,v)$-subtree: this is for instance the case of
a leaf $v$ which is not a sink such that $(u,v)\in{\cal\hat{A}}$. Finiteness
of the return flow characterizes the subtrees that are stopping as stated in
4.9.

######  Lemma 4.9.

Given a stopping tree-like multigraph $G$ and $(u,v)\in{\cal\hat{A}}$, the
$(u,v)$-subtree $T_{(u,v)}$ is stopping if and only if for any rotor
configuration on $G$, the return flow of $(u,v)$ is finite.

######  Proof 4.10.

If the $(u,v)$-subtree is stopping, then by 2.11 any rotor walk is finite, and
the return flow is finite.

If the $(u,v)$-subtree is not stopping, there is a sink component $C$ in
$T_{(u,v)}$. If $C$ does not contain $u$, it is also a sink component of $G$
since we do not add or remove any arc in $C$ while going from $T_{(u,v)}$ to
$G$. But $G$ is assumed stopping hence such sink component does not exist. The
only possibility is that $C$ contains $u$. In $C$, there is a vertex that will
be visited infinitely often while processing a maximal rotor walk. But this
will be the case for its neighbours in $C$ as well, and, transitively, for
every vertex in $C$. In particular $u$ will be visited infinitely often, hence
for any rotor configuration $\rho$, $r_{\rho}(u,v)$ is infinite.

We give a bound on the maximal value of the return flow in a multigraph as it
will be used to express our complexity results later.

######  Lemma 4.11 (Return flow bound).

Let $(u,u_{1})\in\hat{{\cal A}}$ and $\rho$ be a configuration. Then if there
is a directed path $[u,u_{1},\dots,u_{k},s]$ from $u$ to a sink $s\in S_{0}$
then $r_{\rho}(u,u_{1})$ satisfies

$r_{\rho}(u,u_{1})\leq\prod_{i=1}^{k}|{\cal A}^{+}(u_{i})|\leq e^{|{\cal
A}|/e},$

otherwise $r_{\rho}(u,u_{1})$ is infinite. In particular this shows that
return flows can be written in at most $O(|\cal A|)$ bits.

######  Proof 4.12.

The first inequality derives straightforwardly from the proof of 2.11. A
similar bound can be found in Lemma 1 in [10].

For the second inequality, the previous bound has maximal value if all
vertices on the path have $|{\cal A}|/n$ outgoing arcs with $n$ the number of
vertices. This is maximal for $n=|{\cal A}|/e$ in which case the bound becomes
$e^{|{\cal A}|/e}$. Hence, the return flow can be written in $O(|\cal A|)$
bits.

Return flows and flows are linked by the following result:

######  Lemma 4.13.

Given a stopping tree-like rotor multigraph $G$, consider $u\in V_{0}$ and
suppose that $h(D(\rho)(u))=v$. Then:

  * •

$F_{\rho}(u,v)=r_{\rho}(u,v)$ ;

  * •

for all $w\in\Gamma^{+}(u)\setminus\\{v\\},\quad F_{\rho}(u,w)<r_{\rho}(u,w)$;

  * •

for all
$w\in\Gamma^{+}(u)\cap\Gamma^{-}(u)\setminus\\{v\\},r_{\rho}(w,u)=F_{\rho}(u,w)+1$.

######  Proof 4.14.

Let $\rho^{\prime}$ be the configuration obtained after routing a particle
from $(\rho,u)$ until the particle is on $u$ for the last time, in which case
$h(\rho^{\prime}(u))=v$ and $r_{\rho^{\prime}}(u,v)=1$. By definition of
$\rho^{\prime}$, we have $F_{\rho^{\prime}}(u,v)=1$ and
$F_{\rho^{\prime}}(u,w)=0$ for all $w\in\Gamma^{+}(u)\setminus\\{v\\}$. If,
moreover, $w\in\Gamma^{-}(u)$ then
$r_{\rho^{\prime}}(w,u)=1=1+F_{\rho^{\prime}}(u,w)$. Hence
$r_{\rho^{\prime}}(u,v)=1=F_{\rho^{\prime}}(u,v)$ and by definition of the
return flow, $r_{\rho^{\prime}}(u,w)\geq 1$ so that
$r_{\rho^{\prime}}(u,w)>F_{\rho^{\prime}}(u,w)$. Hence the property is
satisfied for $\rho^{\prime}$.

On the other hand it should be clear that
$F_{\rho}(u,w)-F_{\rho^{\prime}}(u,w)=r_{\rho}(u,w)-r_{\rho^{\prime}}(u,w)$
for every $w\in\Gamma^{+}(u)$. If, moreover, $w\in\Gamma^{-}(u)$ and $w\neq v$
the previous quantity is also equal to $r_{\rho}(w,u)-r_{\rho^{\prime}}(w,u)$.
Hence the property is true for $\rho$ as well.

$u_{1}$$u_{3}$$s_{0}$ $u_{4}$$u_{0}$$u_{2}$$s_{1}$ 2223222$+\infty$1010 Figure
6: Examples of return flows in a simple graph. The rotor configuration is
depicted by red arcs in dashes, with $S_{0}=\\{s_{0},s_{1}\\}$, and
$\theta_{u_{i}}$ is the anticlockwise order on every vertex. We write the
return flow of all arcs of $\hat{{\cal A}}$ next to their corresponding arc in
${\cal A}$. As a tutorial example, we detail the computation of
$r_{\rho}(u_{1},u_{0})$ and $r_{\rho}(u_{0},u_{1})$. In the
$(u_{1},u_{0})$-subtree, the particle will visit the following sequence of
vertices $u_{1},u_{0},u_{2},u_{0},u_{1},u_{0},u_{4},u_{0},u_{2},s_{1}$, where
it crosses $(u_{1},u_{0})$ twice, thus $r_{\rho}(u_{1},u_{0})=2$. For the
$(u_{0},u_{1})$-subtree, the sequence of vertices visited by the particle is
$u_{0},u_{1},u_{0},u_{1},u_{3},u_{1},u_{0},u_{1},u_{3},s_{0}$ hence
$r_{\rho}(u_{0},u_{1})=3$.

###  4.3 Revolving Routine

Based on the foregoing, using 4.13, in order to calculate $D(\rho)(v)$, we
need to compute the flow of all arcs $(u,w)$ with $w\in\Gamma^{+}(u)$ and
compare it to $r_{\rho}(u,w)$. This idea is introduced in the example drawn in
Figure 7.

$u$$v_{1}$$T_{1}$$v_{2}$$T_{2}$$v_{3}$$T_{3}$44$+\infty$ Figure 7: Consider
the same stopping tree-like rotor multigraph as in Figure 5 where $\rho(u)$ is
the red arc in dashes. The return flow of all arcs of $\hat{{\cal A}}^{+}(u)$
are given next to their corresponding arcs in ${\cal A}$.

In Figure 7, let us put a particle on $u$ and route it until it comes back to
$u$. The first time, the particle will travel through the red arc in dashes
and land on $v_{3}$. Then, the red arc in dashes (i.e. $\rho(u)$) is updated
to $\theta_{u}(\rho(u))$ which is the other arc with tail $u$ and head
$v_{3}$. As $r_{\rho}(u,v_{3})>1$, the particle does not reach a sink in
$T_{3}$, and the particle will come back to $u$ after travelling in $T_{3}$.
After this process (the particle’s walk in $T_{3}$), the return flow of
$(u,v_{3})$ has decreased by one as $(u,v_{3})$ has been crossed exactly once.
During the next step of this rotor walk, the particle will travel to $v_{3}$
again, make several moves in $T_{3}$ without reaching a sink and comes back to
$u$. The return flow of $(u,v_{3})$ is now $2$. Next, the particle will travel
to $v_{2}$ and so on. At some point, the particle will travel through an arc
with tail $u$ and head $v_{i}$ while the return flow of $(u,v_{i})$ is one. In
this case, the particle will reach a sink in $T_{i}$ and then will not come
back to $u$. Here this condition is first met for $i=3$ when the return flows
of $(u,v_{1}),(u,v_{2}),(u,v_{3})$ respectively are $2,+\infty,1$ the last
time the particle is on vertex $u$.

Inspired by this process, we state the following Theorem.

######  Theorem 4.15.

For any vertex $u\in V_{0}$, given the return flows of all arcs
$(u,v)\in\hat{A}$ with $v\in\Gamma^{+}(u)$, one can compute $D(\rho)(u)$ and
the flow on each arc $(u,v)$ in time

$O(|\Gamma^{+}(u)|\leavevmode\nobreak\ \cdot\leavevmode\nobreak\
c(r_{\max},|{\cal A}^{+}(u)|))$

with $r_{\text{max}}$ being the maximum (finite) value of $r_{\rho}(u,v)$ for
all $v\in\Gamma^{+}(u)$.

######  Proof 4.16.

algorithm 1 is a local routine that abstracts the process described in the
caption of Figure 5. It computes $D(\rho)(u)$ as $a$ and the flow of all arcs
$(u,v)$ as $F$. Notice that, in the routine and its improved version, we
consider that $+\infty-1$ and $+\infty/a$ with $0<a<+\infty$ are equal to
$+\infty$. Remark also that, since the input multigraph $G$ of the routine is
stopping, there is at least one return flow which is finite. However, since
the return flow can be exponential as in the example drawn in Figure 2,
algorithm 1 might run in exponential time.

input : $u$ is a vertex of $V$;
$r:\Gamma^{+}(u)\rightarrow\mathbb{Z}\cup\\{+\infty\\}$ contains the return
flows of arcs $(u,v)$ of $\hat{{\cal A}}$ with $v\in\Gamma^{+}(u)$.

output : $a$ an arc of ${\cal A}^{+}(u)$; $F$ such that $F(v)$ is the number
of times an arc of ${\cal A}^{+}(u)$ with head $v$ has been visited

1 $F(v)\leftarrow 0$ for all $v\in\Gamma^{+}(u)$

2 $a\leftarrow\rho(u)$

3 while  _$r(h(a)) >1$_ do

4

5 $r(h(a))\leftarrow r(h(a))-1$

6 $F(h(a))\leftarrow F(h(a))+1$

7 $a\leftarrow\theta_{u}(a)$

8

return _$a$ , $F$_

Algorithm 1 Revolving Routine

We can speed up the computation by noting that every time the rotor at $u$
makes one full turn, we know exactly how many times each value of the flow $F$
has increased. This remark leads to the improved algorithm 2 denoted by IRR in
the rest of the document. The IRR consists in two steps. First, we compute how
many full turns the rotor on $u$ does before the routine ends. Then, we use
algorithm 1.

input : $u$ is a vertex of $V$;
$r:\Gamma^{+}(u)\rightarrow\mathbb{Z}\cup\\{+\infty\\}$ contains the return
flows of arcs $(u,v)$ of $\hat{{\cal A}}$ with $v\in\Gamma^{+}(u)$.

output : $a$ an arc of ${\cal A}^{+}(u)$; $F$ such that $F(v)$ is the number
of times an arc of ${\cal A}^{+}(u)$ with head $v$ has been visited

1 For $v\in\Gamma^{+}(u)$, let $Q(v)$ be the quotient of the euclidean
division of $r(v)$ by $|h^{-1}(v)|$; let $q_{\text{min}}$ be the minimum value
of $Q(v)$ for all $v$; let $R(v)$ be $r(v)-(q_{\text{min}}*|h^{-1}(v)|)$ and
let $F(v)=0$.

/* This step corresponds to the return flow diminutions that occurs during the
$q_{\text{min}}*|{\cal A}^{+}(u)|$ first steps, and it also ensures that there
exists at least one $v$ such that in less than $|{\cal A}^{+}(u)|$ steps,
$R(v)<1$. */

2 $a\leftarrow\rho(u)$

3

4while  _$R(h(a)) >1$_ do

5 $R(h(a))\mathrel{-}=1$

6 $a\leftarrow\theta_{u}(a)$

7

8for  _$v\in\Gamma^{+}(u)$_ do

9 $F(v)\leftarrow r(v)-R(v)$

10

return _a,F_

Algorithm 2 Improved Revolving Routine (IRR)

At line 1 of IRR, computing $Q(v)$ is done in time
$O\big{(}|\Gamma^{+}(u)|\leavevmode\nobreak\ \cdot\leavevmode\nobreak\
c(r_{\max},|{\cal A}^{+}(u)|)\big{)}$. Then, the loop at line 3 stops in at
most $|{\cal A}^{+}(u)|$ steps, which is small compared to the first term. The
same applies for the loop at line 6. In the end, IRR runs in time
$O(|\Gamma^{+}(u)|\leavevmode\nobreak\ \cdot\leavevmode\nobreak\
c(r_{\max},|{\cal A}^{+}(u)|))$.

As the routines are crucial for the rest of the article, we now state an
important monotony property. Here, we fix a vertex $v$ in $G$ and consider on
the outgoing arcs of $v$ the respective return flows $r_{1}$ and $r_{2}$ of
two rotor configurations $\rho_{1}$ and $\rho_{2}$.

######  Lemma 4.17 (Monotony of the flow).

Let $u\in V_{0}$, and $\rho_{1},\rho_{2}$ be two rotor configurations such
that $\rho_{1}(u)=\rho_{2}(u)$. Let $v_{i}=h(D(\rho_{i})(u))$ for
$i\in\\{1,2\\}$ and $\overline{\Gamma}$ be the set of vertices
$v\in\Gamma^{+}(u)$ such that $r_{\rho_{1}}(u,v)\geq r_{\rho_{2}}(u,v)$. If
$v_{1}\in\overline{\Gamma}$, then

  * •

$F_{\rho_{1}}(u)\geq F_{\rho_{2}}(u)$ component-wise,

  * •

$v_{2}\in\overline{\Gamma}$.

######  Proof 4.18.

Let $\rho_{i}^{k}$ for $i\in\\{1,2\\}$ be the rotor configuration after the
particle has visited $u$ exactly $k$ times during a maximal rotor walk
starting from $(\rho_{i},u)$. In particular, $\rho_{i}^{1}=\rho_{i}$. We
denote by $R_{i}^{k}(u,v)$ and $F_{i}^{k}(u,v)$ the quantities
$r_{\rho_{i}^{k}}(u,v)$ and $F_{\rho_{i}^{k}}(u,v)$ respectively. Let $K_{i}$
be the last time the particle is on $u$ in this walk, which is characterized
by $R^{K_{i}}_{i}(u,v_{i})=1$ and $h(\rho_{i}^{K_{i}}(u))=v_{i}$ for
$i\in\\{1,2\\}$.

For all $k\leq\min(K_{1},K_{2})$, let $\overline{\Gamma}^{k}$ be the set of
vertices $v\in\Gamma^{+}(u)$ such that $R_{1}^{k}(u,v)\geq R_{2}^{k}(u,v)$. It
turns out that in fact, for all such $k$ we have
$\overline{\Gamma}^{k}=\overline{\Gamma}$ since values of both $R_{1}$ and
$R_{2}$ are decremented simultaneously.

We first show that $K_{2}\leq K_{1}$. By contradiction, assume that
$K_{2}>K_{1}$. Since $v_{1}\in\overline{\Gamma}$, then, at step $K_{1}$,
$R^{K_{1}}_{1}(u,v_{1})=1\geq R^{K_{1}}_{2}(u,v_{1})$ and
$h(\rho_{i}^{K_{i}}(u))=v_{1}$ for $i\in\\{1,2\\}$. This implies that $K_{1}$
is the last time that the walk starting at $(\rho_{2},u)$ is at $u$, _i.e._
$K_{2}=K_{1}$, hence a contradiction.

For every $v\in\Gamma^{+}(u)$, we have $F_{\rho_{i}}(u,v)=\Delta
F^{k}_{i}(u,v)+F^{k}_{i}(u,v)$ with $\Delta
F^{k}_{i}(u,v)=F_{\rho_{i}}(u,v)-F^{k}_{i}(u,v)$. $\Delta F^{k}_{i}(u,v)$ is
the number of times each arc $(u,v)$ has been used until step $k$. Since
$\rho_{1}(u)=\rho_{2}(u)$, and as long as $k\leq K_{2}$, $\Delta
F^{k}_{i}(u,v)$ does not depend on $i$. It follows that
$F_{\rho_{1}}(u,v)-F_{\rho_{2}}(u,v)=F^{K_{2}}_{1}(u,v)-F^{K_{2}}_{2}(u,v)$.
If $v\neq v_{2}$ then
$F^{K_{2}}_{1}(u,v)-F^{K_{2}}_{2}(u,v)=F^{K_{2}}_{1}(u,v)-0\geq 0$. Otherwise
$F^{K_{2}}_{1}(u,v_{2})-F^{K_{2}}_{2}(u,v_{2})=F^{K_{2}}_{1}(u,v_{2})-1$.
Since $K_{1}\geq K_{2}$ and $h(\rho_{1}^{K_{2}}(u))=v_{2}$, arc $(u,v_{2})$
will be used at least once more during the walk, _i.e._
$F^{K_{2}}_{1}(u,v_{2})\geq 1$. Hence the difference is positive which shows
the first part of the lemma.

Let $v$ be such that $v\notin\overline{\Gamma}$. Then
$R_{2}^{K_{2}}(u,v)>R_{1}^{K_{2}}(u,v)\geq 1$. Hence $R_{2}^{K_{2}}(u,v)\geq
2$ which implies $v_{2}\neq v$ and then $v_{2}\in\overline{\Gamma}$.

##  5 ARRIVAL for Tree-like Multigraphs

In this section we show that, for a given configuration $\rho$, we can compute
the Destination Forest $D(\rho)$ in time complexity $O(|{\cal A}|\cdot
c(r_{\max},|{\cal A}|))$, hence solve the ARRIVAL problem for every vertex at
the same time. To achieve this, we recursively compute return flows for all
arcs in $\hat{{\cal A}}$ and then use these flows to compute the destination
forest.

In all this section, let $G=(V_{0},S_{0},{\cal A},h,t,\theta)$ be a stopping
tree-like rotor multigraph and $\rho$ be a rotor configuration on $G$.

The next two lemmas show how to compute the return flows by using Theorem
4.15.

######  Lemma 5.1.

For any two vertices $u$ and $v$ such that $(u,v)\in\hat{{\cal A}}$, and given
$r_{\rho}(v,w)$ for every $w\in\Gamma^{+}(v)\setminus{\\{u\\}}$, the return
flow $r_{\rho}(u,v)$ can be computed in time $O(|\Gamma^{+}(v)|\cdot
c(r_{\max},|{\cal A}^{+}(v)|))$. We illustrate this operation in Figure 8.

######  Proof 5.2.

If $(v,u)\not\in\hat{{\cal A}}$, then $r_{\rho}(u,v)=1$.

Otherwise, if $r_{\rho}(v,w)=+\infty$ for all $w\in\Gamma^{+}(v)$ such that
$w\neq u$, then $r_{\rho}(u,v)=+\infty$.

In all other cases, apply the IRR to the vertex $v$, with input values
$r_{\rho}(v,w)$ for all $w\in\Gamma^{+}(v)$ such that $w\neq u$, and with
$r_{\rho}(v,u)=p$, where $p$ is intended to be an integer large enough so that
the output $a$ of the IRR is such that $h(a)\neq u$. Then by 4.13,
$r_{\rho}(u,v)=F_{\rho}(v,u)+1$, where $F_{\rho}(v)$ is obtained by the IRR.

Parameter $p$ in the previous proof should be chosen large enough so that
variable $R(u)$ in the routine remains strictly positive; for instance $p$ can
be initialized with $(q_{\text{min}}+1)\cdot|h^{-1}(u)|$ with $q_{\text{min}}$
defined in algorithm 2.

$u$$v_{1}$$v_{3}$$v_{4}$$v_{2}$r$\bm{r_{a}}$$\bm{r_{b}}$$\bm{r_{c}}$

Figure 8: In this Figure, we illustrate which value is computed with 5.1. If
the return flows $r_{a},r_{b},r_{c}$ are known, we can compute the return flow
$r$.

.

######  Lemma 5.3.

For any vertex $u\in V_{0}$, and given $r_{\rho}(u,v)$ for every
$v\in\Gamma^{+}(u)$, one can compute the return flow of all arcs $(w,u)$ with
$w\in\Gamma^{-}(u)$ in time $O(|\Gamma^{+}(u)|\cdot c(r_{\max},|{\cal
A}^{+}(u)|))$. We illustrate this operation in Figure 9.

######  Proof 5.4.

For all $w\in\Gamma^{-}(u)\setminus{\Gamma^{+}(u)}$, we have
$r_{\rho}(w,u)=1$.

We use Theorem 4.15 once on $u$ to compute $D(\rho)(u)$ and the vector flow
$F_{\rho(u)}$. Let $v=h(D(\rho)(u))$. Then, by 4.13, for all
$w\in\Gamma^{-}(u)\cap\Gamma^{+}(u)\setminus{v}$, we have
$r_{\rho}(w,u)=F_{\rho}(u,w)+1$. It remains to apply 5.1 once more to compute
$r_{\rho}(v,u)$. All in all, we have used Theorem 4.15 twice, hence the
complexity.

One can check by applying 5.3 that, on the example of Figure 7, we have
$r_{\rho}(v_{1},u)=3$, $r_{\rho}(v_{2},u)=2$ and $r_{\rho}(v_{3},u)=4$.

$u$$v_{1}$$v_{3}$$v_{4}$$v_{2}$$\bm{r_{d}}$$\bm{r_{a}}$$\bm{r_{b}}$$\bm{r_{c}}$$\bm{r_{1}}$$\bm{r_{2}}$$\bm{r_{3}}$$\bm{r_{4}}$

Figure 9: In this Figure, we illustrate which values is computed with 5.3. If
the return flows $r_{a},r_{b},r_{c},r_{d}$ are known, we can compute the
return flows $r_{1},r_{2},r_{3},r_{4}$.

.

We are now ready to state our main theorem. Complexity bounds are given in two
different contexts:

  * •

a context where the time needed for arithmetic computation matters, as in a
Turing machine. These bounds are polynomial in the size of the graph and use
notation $c(a,b)$ to denote the time complexity of dividing the number $a$ by
the number $b$;

  * •

another context where arithmetic operations can be done in constant time,
where we achieve linear complexity in the size of the graph.

######  Theorem 5.5 (Complete Destination Algorithm).

The configuration $D(\rho)$ can be computed in time $O(|{\cal A}|)$ for a
stopping tree-like multigraph in a model where arithmetic operations can be
made in constant time, or alternatively in $O(|{\cal A}|\cdot
c(r_{\max},|{\cal A}|))$ on a Turing Machine.

######  Proof 5.6.

Consider an arbitrary vertex $x$. We proceed to a Breadth-First Search (BFS)
starting from $x$ in $\overline{G}$, the simple undirected graph associated
with $G$. Let $e_{1},e_{2},\dots,e_{m}$ (resp. $u_{0},u_{1},\dots,u_{k}$ with
$u_{0}=x$) be the prefix order on the edges (resp. on the vertices) of
$\overline{G}$ obtained during the BFS, i.e. the order in which the edges
(resp. the vertices) are visited.

The algorithm is split into two phases:

  1. 1.

Computation of return flows for all arcs directed from $x$ towards the leaves:
for $t=m,m-1,\dots,2,1$, if the edge $e_{t}$ corresponds to an existing arc
$(u_{i},u_{j})$ of $\hat{{\cal A}}$, such that $(u_{i},u_{j})$ is directed
from $x$ towards a leaf of $G$, consider two cases. Firstly, if $u_{j}$ is a
leaf, then store that either $r_{\rho}(u_{i},u_{j})=1$ or
$r_{\rho}(u_{i},u_{j})=+\infty$ depending on whether $u_{j}\in S_{0}$ or not.
Secondly, if $u_{j}$ is not a leaf, then by definition of a BFS and a prefix
order, if an arc $(u_{j},v)$ with $v\neq u_{i}$ corresponds to an edge
$e_{t^{\prime}}$, then $t<t^{\prime}$. Hence, we already know the value of
$r_{\rho}(u_{j},v)$ for every $v\neq u_{i}$ with $v\in\Gamma^{+}(u_{j})$. This
means that we can compute recursively $r_{\rho}(u_{i},u_{j})$ by 5.1.

  2. 2.

Computation of return flows of all arcs directed from the leaves towards $x$:
when this phase begins, for any vertex $u$ except $x$, all return flows
$r_{\rho}(u,v)$ for all $v\in\Gamma^{+}(v)$ are known, excepted the return
flow of the arc directed from $u$ to $x$. We use 5.3 applied to vertices
$u_{i}$ in increasing order on $i$ as it guarantees that the conditions to
apply 5.3 are met. Furthermore, we also compute $D(\rho)(u_{i})$ at the same
time.

The time needed for the BFS part is $O(|\hat{{\cal A}}|+|V|)$.

In the first phase, we use Theorem 4.15 at most once for every vertex $v$, for
the arc $(u,v)$ coming from $x$ towards the leaves. During the second phase,
we we use Theorem 4.15 at most twice for each vertex. All in all, we use
Theorem 4.15 three times for each vertex. Hence the time complexity is
$O(\sum_{v\in V}{(|\hat{{\cal A}}^{+}(v)|\cdot c(r_{\max},|{\cal A}|)))}$
which amounts to $O(|{\cal A}|\cdot c(r_{\max},|{\cal A}|))$.

We showed in 4.11 that return flows could be written in at most $O(|{\cal
A}|)$ bits which gives an upper bound for $c(r_{\max},|{\cal A}|)$ of $k|{\cal
A}|\log(|{\cal A}|)$ for some constant $k>0$. It is proved in [13] that the
multiplication of two $n$ bits integers can be done in time $O(n\log(n))$ and
as the complexity of the division is equivalent to the complexity of
multiplication (see [4]), the bound follows. Thus the complexity of our
algorithm is $O(|{\cal A}|^{2}\log(|{\cal A}|))$ in this context.

##  6 One-player Rotor Game

Problem ARRIVAL can be seen as a zero-player game where the winning condition
is that the particle reaches a particular sink (or set of sinks). The one and
two players variants of ARRIVAL (i.e. deterministic analogs of _Markov
decision processes_ and _Stochastic games_) we address in the next sections
are inspired from [18], but differ by the choice of the set of strategies (see
the discussion hereafter).

In this section, we specifically consider a game with a single player that
controls a subset of vertices $V_{{\cal MAX}}$ of $V_{0}$. Given a rotor
configuration on the rest of the vertices of $V_{0}$, a starting vertex and an
integer value for each sink, his goal is to wisely choose the initial rotor
configuration of the vertices he controls (his strategy) such that the
particle reaches one of the sinks with maximal value.

A remark is in order here: in the seminal paper [18], a strategy is defined in
a more general way since it consists in choosing an outgoing-arc each time the
particle is on a vertex controlled by the player. In particular, for a given
vertex, the sequence of arcs may not follow a rotor rule, and the number of
strategies is even unbounded. It has been shown in that paper that solving
such game is NP-complete. On the one hand, the given reduction of 3-SAT can
easily be adapted to fit to our framework showing that our definition of the
game, although simpler since the set of strategies is finite, still leads to
an NP-complete problem. On the other hand, our results extend naturally to
general strategies, but at the cost of more technicalities. For instance, the
use of general strategies may lead to non-stopping rotor graphs even if every
vertex is connected to a sink. This case also seems to us a very natural
extension of the zero player case.

To formally define the game, we introduce the following definition.

######  Definition 6.1 (Partial Configuration).

Let $V^{\prime}$ be a subset of $V_{0}$, a _partial rotor configuration_ on
$V^{\prime}$ is a mapping $\rho^{\prime}$ from $V^{\prime}$ to ${\cal A}$ such
that $\rho^{\prime}(u)\in{\cal A}^{+}(u)$ for all $u\in V^{\prime}$.

A one-player rotor game (resp. one-player tree-like rotor game) is given by
$(V_{r},V_{{\cal MAX}},S_{0},{\cal A},h,t,\theta,\text{val},\rho)$ where
$V_{r}$, $V_{{\cal MAX}}$ and $S_{0}$ are disjoint sets of vertices, such that

  * •

$(V_{0},S_{0},{\cal A},h,t,\theta)$ is a rotor graph (resp. tree-like rotor
graph) with $V_{0}=V_{r}\cup V_{{\cal MAX}}$;

  * •

val is a map from $S_{0}$ to $\mathbb{N}$ corresponding to a utility of the
player who wants the particle to reach a sink $s$ with the highest possible
value $\text{val}(s)$;

  * •

$\rho$ is a partial configuration on $V_{r}$, the initial configuration on the
vertices not controlled by the player.

The tree-like rotor game is _stopping_ if and only if the induced rotor graph
$(V_{0},S_{0},{\cal A},h,t,\theta_{v})$ is stopping.

The player is called ${\cal MAX}$, and a _strategy_ for ${\cal MAX}$ is a
partial rotor configuration on $V_{{\cal MAX}}$. We denote by $\Sigma_{{\cal
MAX}}$ the finite set of strategies for this player.

Consider a partial rotor configuration $\rho$ on $V_{r}$ together with
strategy $\sigma$ and denote by $(\rho,\sigma)$ the rotor configuration where
we apply the partial configuration $\rho$ or $\sigma$ depending on whether the
vertex is in $V_{r}$ or $V_{{\cal MAX}}$.

The value of the game for strategy $\sigma$ and starting vertex $u_{0}$ is
denoted by $\text{val}_{\sigma}(u_{0})$ and is equal to $\text{val}(s)$ where
$s$ is the sink reached by a maximal rotor walk from the rotor particle
configuration $((\rho,\sigma),u_{0})$ if any, and $0$ otherwise. As in the
zero-player framework, up to computing strongly connected components that do
not contain sinks and replacing each of them with a sink of value $0$, we can
suppose that the tree-like rotor game is stopping. In the following, all rotor
games we consider are tree-like and stopping unless stated otherwise.

When $u_{0}$ is fixed, the maximal value of $\text{val}_{\sigma}(u_{0})$ over
all strategies $\sigma\in\Sigma_{{\cal MAX}}$ is called the _optimal value_ of
the game with starting vertex $u_{0}$ and is denoted by
$\text{val}^{*}(u_{0})$. Any strategy $\sigma\in\Sigma_{{\cal MAX}}$ such that
$\text{val}_{\sigma}(u_{0})=\text{val}^{*}(u_{0})$ is called an _optimal
strategy_ for the game starting in $u_{0}$. Observe that optimal strategies
may depend on the choice of $u_{0}$ as illustrated in Figure 10. The one-
player ARRIVAL problem consists in computing the optimal value of a given
starting vertex in a one-player rotor game.

$g$$u$$1$ $v$$1$ $0$ $0$ Figure 10: Simple graph where the optimal strategy
depends on the starting vertex $u_{0}$, with $V_{{\cal MAX}}=\\{g\\}$, with
$u,v\in V_{0}$ and with all other vertices being sinks. As in previous
examples, the starting configuration is depicted by red arcs in dashes, and
the rotor order on all vertices is an anticlockwise order on their outgoing
arcs. In the case $u_{0}=v$, the only optimal strategy is $\sigma(g)=(g,v)$
and the game has value $1$. In the case $u_{0}=u$, the only optimal strategy
is $\sigma(g)=(g,u)$ and the game has value $1$.

First, we study the case where the values of the sinks are binary, then we
adapt those results to the case of nonnegative integer values, and finally we
present our results for some different set of strategies.

###  6.1 One-player Binary Rotor Game

In this subsection, we restrict the game to the case where values of sinks are
binary numbers i.e. $\text{val}(s)\in\\{0,1\\}$ for all $s\in S_{0}$. Recall
that in the tree-like rotor graph, $T_{(u,v)}$ denotes the $(u,v)$-subtree. We
extend this notation to denote the one-player, not necessarily stopping, game
played on the $(u,v)$-subtree where we restrict $V_{{\cal MAX}}$ and $V_{r}$
to the subtree. For this game, we only consider the case where the starting
vertex is $u$.

######  Definition 6.2 (Value under strategy).

Let $(u,v)$ be an arc of $\hat{{\cal A}}$. Given a strategy $\sigma$ for the
$(u,v)$-subtree, we denote by $\text{val}_{\sigma}(u,v)$ (resp.
$\text{val}^{*}(u,v)$) the value of the game under strategy $\sigma$ (resp.
under an optimal strategy) in $T_{(u,v)}$. This is called the value (resp. the
optimal value) of the arc $(u,v)$ for strategy $\sigma$.

######  Definition 6.3 (Optimal return flow $r^{*}$).

Let $(u,v)$ be an arc of $\hat{{\cal A}}$. If $\text{val}^{*}(u,v)=0$, then
$r^{*}(u,v)$ is defined as the maximum of $r_{\sigma}(u,v)$ over all
strategies $\sigma$ on $T_{(u,v)}$, otherwise it is the minimum of
$r_{\sigma^{*}}(u,v)$ among _optimal_ strategies $\sigma^{*}$ on $T_{(u,v)}$.

The next lemma connects the value $\text{val}_{\sigma}(u)$ with the value of
the last outgoing arc of vertex $u$ while processing a maximal rotor walk from
the rotor-particle configuration $((\rho,\sigma),u)$.

######  Lemma 6.4.

Let $a$ be an arc of ${\cal A}^{+}(u)$ such that $D(\rho,\sigma)(u)=a$ with
$h(a)=v$. We have $\text{val}_{\sigma}(u)=\text{val}_{\sigma}(u,v)$.

To recursively compute an optimal strategy, we need a stronger notion of
optimality, namely a _subtree optimal strategy_.

######  Definition 6.5 (Subtree optimal strategy).

A strategy $\sigma^{*}$ is _subtree optimal_ at $u_{0}$ if it is optimal at
$u_{0}$ and, moreover, $\text{val}_{\sigma^{*}}(u,v)=\text{val}^{*}(u,v)$ and
$r_{\sigma^{*}}(u,v)=r^{*}(u,v)$ for every $(u,v)$-subtree such that $(u,v)$
is directed from $u_{0}$ towards the leaves.

Instead of recursively computing only the return flow as in the zero-player
game, we now propagate both the optimal value and the optimal return flow to
construct a subtree optimal strategy. Here, we give an equivalent to 5.1 for
the one-player game that details how to recursively compute $\text{val}^{*}$
and $r^{*}$.

######  Lemma 6.6.

Let $(u,v)\in\hat{{\cal A}}$. For every $(v,w)$-subtree with
$w\in\Gamma^{+}(v)\setminus\\{u\\}$, assume that there is a strategy
$\sigma^{*}_{w}$ that is subtree optimal. Let $\sigma_{v}$ be a strategy on
the $(u,v)$-subtree $T_{(u,v)}$ such that $\sigma_{v}(z)=\sigma^{*}_{w}(z)$
when $z\in T_{(v,w)}\cap V_{{\cal MAX}}$ and $z\neq v$. Furthermore, if $v\in
V_{{\cal MAX}}$, let $\Sigma_{v}$ be the set of strategies defined on
$T_{(u,v)}$ that agree with $\sigma_{v}$ on every vertex but $v$. We consider
two cases:

  * •

if $\text{val}^{*}_{(u,v)}=0$, $\sigma_{v}(v)$ is a strategy in $\Sigma_{v}$
that maximizes the return flow on $(u,v)$;

  * •

if $\text{val}^{*}_{(u,v)}=1$, $\sigma_{v}(v)$ is a strategy in $\Sigma_{v}$
that is optimal and minimizes the return flow on $(u,v)$.

Then $\sigma_{v}$ is subtree optimal on $T_{(u,v)}$.

######  Proof 6.7.

We suppose that $v\in V_{{\cal MAX}}$. The case $v\notin V_{{\cal MAX}}$ can
be treated similarly and is omitted.

By assumption, the restriction of $\sigma_{v}$ to every subtree $T_{(w,z)}$,
where $(w,z)$ is an arc of $T_{(u,v)}$ different from $(u,v)$, and directed
from $u$ towards the leaves, is subtree optimal. It remains to show that
$\text{val}_{\sigma_{v}}(u,v)=\text{val}^{*}(u,v)$ and
$r_{\sigma_{v}}(u,v)=r^{*}(u,v)$.

  * •

Assume that $\text{val}^{*}(u,v)=0$. In this case, we have
$\text{val}_{\sigma_{v}}(u,v)=\text{val}^{*}(u,v)=0$ as for any strategy.

For the return flow, we consider different cases.

If $(v,u)\notin\hat{{\cal A}}$, then $r_{\sigma}(u,v)=1$ for every strategy
$\sigma$ on $T_{(u,v)}$, so $r_{\sigma_{v}}(u,v)=1=r^{*}(u,v)$ is maximal. If
$(v,u)\in\hat{{\cal A}}$ and $r^{*}(v,w)=+\infty$ for every
$w\in\Gamma^{+}(v)\setminus\\{u\\}$, then $r_{\sigma}(u,v)=+\infty$ for every
strategy $\sigma$ on $T_{(u,v)}$, in particular
$r_{\sigma_{v}}(u,v)=+\infty=r^{*}(u,v)$.

Finally, if $(v,u)\in\hat{{\cal A}}$ and there is $w$ such that
$r^{*}(v,w)<+\infty$, let $w_{0}=h(D(\rho,\sigma_{v})(v))$ (defined in the
stopping rotor graph $T_{(u,v)}$) and consider a strategy $\sigma$ defined on
$T_{(u,v)}$ with $\sigma(v)=\sigma_{v}(v)$. By 6.4, we have
$\text{val}_{\sigma_{v}}(v)=\text{val}_{\sigma_{v}}(v,w_{0})$ hence
$\text{val}_{\sigma_{v}}(v,w_{0})=0$. Since $\sigma_{v}$ is subtree optimal on
the $(v,w_{0})$-subtree, it follows that $\text{val}^{*}(v,w_{0})=0$ and then
$\text{val}_{\sigma}(v,w_{0})=0$ and finally we have $r_{\sigma}(v,w_{0})\leq
r_{\sigma_{v}}(v,w_{0})$.

We have $\sigma(v)=\sigma_{v}(v)$ and $w_{0}$ is such that
$r_{\sigma}(v,w_{0})\leq r_{\sigma_{v}}(v,w_{0})$. Following 4.17 applied to
$v$, $w_{0}\in\overline{\Gamma}$, and then $F_{\sigma}(v,u)\leq
F_{\sigma_{v}}(v,u)$. By 4.13, we have $r_{\sigma}(u,v)=F_{\sigma}(v,u)+1$ and
$r_{\sigma_{v}}(u,v)=F_{\sigma_{v}}(v,u)+1$. This implies that
$r_{\sigma}(u,v)\leq r_{\sigma_{v}}(u,v)$. Since $\sigma_{v}(v)$ is chosen so
that to maximize the return flow on the set of strategies $\Sigma_{v}$ the
result follows.

  * •

Assume that $\text{val}^{*}(u,v)=1$. We first show that there is an optimal
strategy in $\Sigma_{v}$.

For this, consider an optimal strategy $\sigma^{*}$ on $T_{(u,v)}$ and let
$w_{0}=h(D(\rho,\sigma^{*})(v))$. By 6.4, it follows that
$\text{val}_{\sigma^{*}}(v,w_{0})=1$ and then $\text{val}^{*}(v,w_{0})=1$. Let
$\sigma$ be the strategy in $\Sigma_{v}$ such that $\sigma(v)=\sigma^{*}(v)$.
Since $\sigma$ is subtree optimal on $T_{(v,w_{0})}$ we have
$r_{\sigma^{*}}(v,w_{0})\geq r_{\sigma}(v,w_{0})$. On the other hand, let $W$
be the set of vertices $w\in\Gamma^{+}(v)\setminus\\{u\\}$ such that
$\text{val}^{*}(v,w)=0$. On this set $r_{\sigma^{*}}(v,w)\leq
r_{\sigma}(v,w)$, _i.e._ $w\notin\overline{\Gamma}$ following the notation of
4.17. Hence $D(\rho,\sigma)(v)\notin W$ which implies
$\text{val}_{\sigma}(u,v)=1$.

Now, showing that $r_{\sigma_{v}}(u,v)=r^{*}(u,v)$ is done exactly the same
way as the case $\text{val}^{*}(u,v)=0$.

Note that if $v\in S_{0}$, then there is no decision to make in $T_{(u,v)}$,
and the empty strategy is subtree optimal. Otherwise, 6.6 shows inductively
that such subtree optimal strategy exists for any $T_{(u,v)}$ where
$(u,v)\in\hat{{\cal A}}$.

As a second remark, 6.6 can straightforwardly be adapted to the case where the
player seeks to minimize the value, by swapping the role of subtrees of value
0 and 1. This will be used in next section when we consider a two-player game.

However, this process requires to determine $\sigma_{v}(v)$ which minimizes or
maximizes (depending of the optimal value of arc $(u,v)$) the return flow. To
avoid an additional $|A^{+}(v)|$ factor in the time complexity by trying all
possible choices for $\sigma_{v}(v)$, we propose algorithm 3 which runs in
time $O(|\Gamma^{+}(v)|\cdot c(r_{\max},|{\cal A}|))$. In this algorithm,
$a_{s}$ is an arc that will try all possible starting configurations on $v$ in
the IRR ; whereas $a_{e}$ is the corresponding output arc, i.e. the
destination arc if we start in $a_{s}$. The important fact here is that, when
$a_{s}$ in incremented by $\theta_{v}$, $a_{e}$ possibly moves in the cyclic
ordering but can never make a full turn and go beyond $a_{s}$; this is because
the loop part of the IRR never makes a full turn. During this process, we just
keep track of the maximum and minimum return flows depending on the value of
the subtree in the direction $a_{e}$.

Now, in the same spirit than for the zero-player game, we can use 6.6 as the
basis of a recursive algorithm for computing $\text{val}^{*}(u,v)$ and
$r^{*}(u,v)$ for all $(u,v)\in\hat{{\cal A}}$ directed from $v_{0}$ towards
the leaves. This leads to our main theorem.

######  Theorem 6.8 (Computation of $\text{val}^{*}(u_{0})$).

The optimal value $\text{val}^{*}(u_{0})$ can be computed in the same time
complexity as the computation of $D(\rho)$ in the zero-player game (see
Theorem 5.5).

######  Proof 6.9.

By using 6.6, we recursively compute $\text{val}^{*}(u,v)$ and $r^{*}(u,v)$
for all arcs $(u,v)\in\hat{{\cal A}}$ such that $(u,v)$ is directed from
$u_{0}$ towards the leaves. Several cases are considered:

  * •

if $v\in S_{0}$ then $\text{val}^{*}(u,v)=\text{val}(v)$ and $r^{*}(u,v)=1$;

  * •

otherwise we run algorithm 3.

This process is done at most once for each vertex $v$ which results in the
time complexity given in the statement of the theorem.

It remains to compute $\text{val}^{*}(u_{0})$ knowing
$\text{val}^{*}(u_{0},w)$ and $r^{*}(v_{0},w)$ for every
$w\in\Gamma^{+}(u_{0})$. For this, we run algorithm 3 on arc $(z,u_{0})$ with
$z$ being a fictive vertex such that the only arc incident to $z$ is
$(z,u_{0})$, $r$ and $val$ are $r^{*}(u_{0},w)$ and $\text{val}^{*}(u_{0},w)$
respectively for every $w\in\Gamma^{+}(u_{0})$. Then the binary value returned
by the algorithm is $\text{val}^{*}(z,u_{0})$. But in the $(z,u_{0})$-subtree,
the first step leads the particle to vertex $u_{0}$ and then never goes back
to $z$: the run is then similar to the run starting at $u_{0}$ in the tree-
like rotor game. Hence $\text{val}^{*}(z,u_{0})=\text{val}^{*}(u_{0})$.

Some remarks are in order here. $(i)$ The algorithm used to compute
$\text{val}^{*}(u_{0})$ provides the optimal value of $u_{0}$ as well as a
subtree optimal strategy at $u_{0}$ for every decisional vertex. A tutorial
example is given in Figure 11. $(ii)$ In the case of a simple graph, one can
compute $\text{val}^{*}(u_{0})$ for every vertex $u_{0}$ with the same time
complexity as in Theorem 6.8 as detailed in section 8.

$0$ $u_{0}$$u_{4}$$u_{5}$$1$ $0$$0$ $u_{1}$$u_{2}$$u_{6}$$u_{3}$$1$ (a)
Consider the one-player tree-like rotor game above with $u_{0}$ being the
starting vertex, $V_{{\cal MAX}}=\\{u_{2},u_{4}\\}$ (depicted by squares),
$V_{r}=\\{u_{0},u_{1},u_{3},u_{5},u_{6}\\}$, $\rho$ being the partial
configuration on vertices of $V_{r}$ (depicted by the red arcs in dashes) and
$\theta$ being the anticlockwise order on the outgoing arcs of each vertex
(depicted by the cycling arrow on the right). The set $S_{0}$ contains all
other vertices. Each of these sinks is represented by two circles with its
value written inside.

$0$ $u_{0}$$u_{4}$$u_{5}$$1$$u_{6}$ $0$$0$ $u_{1}$$u_{2}$$u_{3}$$1$
(0,1)(1,1)(1,1)(1,1)(0,1)(0,1)(0,1) (b) We run the first 8 steps that does not
involve a positional vertex of our algorithm recursively from the leaves and
write the couple $(\text{val}^{*}(u,v),r^{*}(u,v))$ next to each arc $(u,v)$
directed from $u_{0}$ towards the leaves.

$0$ $u_{0}$$u_{4}$$u_{5}$$1$$u_{6}$ $0$$0$ $u_{1}$$u_{2}$$u_{3}$$1$
(0,1)(1,1)(1,1)(1,1)(0,1)(0,1)(0,2)(0,1)(1,1)(1,1) (c) We proceed three more
steps of our algorithm and compute $\sigma^{*}(u_{2})$ and $\sigma^{*}(u_{6})$
while doing so. The strategy $\sigma^{*}$ is depicted by blue arcs. From here,
we deduce that $\text{val}^{*}(u_{0})=1$ thanks to Theorem 6.8.

Figure 11: Computation of $\text{val}^{*}$ and $r^{*}$ using Theorem 6.8.

input : $(u,v)$ is an arc of $\hat{{\cal A}}$;
$r:\Gamma^{+}(v)\setminus\\{u\\}\rightarrow\mathbb{Z}\cup{+\infty}$ contains
the optimal return flows of arcs $(v,w)\in\hat{\cal A}$;
$val:\Gamma^{+}(v)\setminus\\{u\\}\rightarrow\\{0,1\\}$ contains the optimal
values of these arcs.

output : an element of ${\cal A}^{+}(v)$ (optimal strategy $\sigma^{*}(v)$); a
positive integer ($r^{*}(u,v)$) and a binary integer ($\text{val}^{*}(u,v)$))

1

2For $w\in\Gamma^{+}(v)$, let $Q(w)$ be the quotient of the euclidean division
of $r(w)$ by $|h^{-1}(w)|$; let $q_{\text{min}}$ be the minimum value of
$Q(w)$ for all $w$; let $R(w)$ be $r(w)-(q_{\text{min}}*|h^{-1}(w)|)$; let
$a_{s}=a_{e}=a_{0}$ with $a_{0}$ being any arc of ${\cal A}^{+}(v)$, let
$f_{0},f_{1},f_{u},value$ be integers initialized to $0$. Let $b_{0},b_{1}$ be
two arcs initialized to $a_{0}$. Let _last_ be a boolean with initial value
False.

3if  _$r(w)=+\infty,\forall w\in\Gamma^{+}(v)\backslash\\{u\\}$_ then

4 return _$b_{0},+\infty,0$_

5repeat

6 if  _$h(a_{e})=u$_ then

7 $f_{u}\mathrel{+}=1$

8 $a_{e}\leftarrow\theta_{v}(a_{e})$

9

10 else

11 $R(h(a_{e}))\mathrel{-}=1$

12 if  _$R(h(a_{e}))=0$_ then

13 if  _$val(a_{e})=0$_ then

/* Keep track of the maximal return with value $0$ */

14 if  _$f_{0} <f_{u}$_ then

15 $f_{0}\leftarrow f_{u}$

16 $b_{0}\leftarrow a_{s}$

17

18 else

19 if  _$f_{1} >f_{u}$_ then

/* Keep track of the minimal with value $1$ and recall the fact that there
exist a strategy with value $1$ */

20 $f_{1}\leftarrow f_{u}$

21 $b_{1}\leftarrow a_{s}$

22

23 $value\leftarrow 1$

24

25 if  _$h(a_{s})=u$_ then

26 $f_{u}\mathrel{-}=1$

27 else

28 $R(h(a_{s}))\mathrel{+}=1$

29

30 $a_{s}\leftarrow\theta_{v}(a_{s})$

31 if  _$\theta_{v}(a_{s})=a_{0}$_ then

32 last $\leftarrow$ True

33 else

34 $a_{e}\leftarrow\theta_{v}(a_{e})$

35

36until  _$a_{s}=a_{0}$ and last=True_

37if  _$value=1$_ then

38 return _$b_{1},f_{1}+q_{\text{min}}*|h^{-1}(u)|+1,1$_

39else

40 return _$b_{0},f_{0}+q_{\text{min}}*|h^{-1}(u)|+1,0$_

Algorithm 3 Optimal Strategy Computation

###  6.2 One-player Integer Rotor Game

We now turn to the case where $\text{val}(s)$ is no longer restricted to be a
binary value. The main difference with the binary case is that there may not
exist a subtree optimal strategy as illustrated in Figure 12. In this example
the value $1$ is an intermediate sink value (neither maximal not minimal),
hence it cannot be decided with the only knowledge of the subtree optimal
strategy on the $(v_{0},v)$-subtree whether the return flow should be
minimized in order to try reaching this sink or maximized if a sink with
higher value can be reached in the rest of the graph. The knowing of
$\text{val}^{*}(u,v)$ and $r^{*}(u,v)$ that was enough in the binary case, is
not sufficient anymore for computing the optimal value recursively. In the
case of simple graphs, we show in subsubsection 8.2.2 that we can add
information on the subtrees in order to compute the optimal value in linear
time complexity, but this technique does not extend to multigraphs.

$u_{0}$$u$$0$ $1$ $2$ Figure 12: Example of a tree-like rotor game that does
not admit a subtree optimal strategy. Here, $u\in V_{{\cal MAX}}$ and
$u_{0}\in V_{r}$. All other vertices belong to $S_{0}$ and their value is
written inside them. The initial configuration of $u_{0}$ is the red arc in
dashes. In the $(u_{0},u)$-subtree, the only optimal strategy is to direct $u$
towards the sink of value $1$ which gives value $1$ with return flow $1$. In
the entire game with starting vertex $u_{0}$, the value of this strategy is
$1$. But the optimal value is $2$ which is obtained by directing $u$ towards
the sink of value $2$.

Despite that, Theorem 6.8 can be used as a basis of a bisection (dichotomy)
method for computing the optimal value. For this, consider the decision
problem of determining whether a sink of value at least $x$ can be reached. We
can solve it by introducing a binary game obtained by replacing all values
that are greater or equal to $x$ by one and the others by zero. It should be
clear that the value of the binary game is one if and only if a sink of value
at least $x$ can be reached in the initial game. All in all, the non-binary
game can be solved in $O(\log(|S_{0}|))$ such iterations. Knowing the optimal
value, say $v^{*}$, an optimal strategy can be computed by solving the binary
associated game where threshold $x$ is chosen equal to $v^{*}$.

###  6.3 One-player Rotor Game: Other Set of Strategies

Here we briefly discuss some variants of this game, where the player can
choose from a different set of strategies than just the initial configurations
on the vertices of $V_{{\cal MAX}}$.

  1. 1.

Let us consider the set of strategies where the player can freely decide the
rotor order on vertices he controls and the starting configuration on it.
Consider an arc $(u,v)\in\hat{{\cal A}}$ and assume that $r^{*}(v,w)$ and
_$\text{val}^{*}(v,w)$_ are known for every $w\in\Gamma^{+}(v)\setminus{u}$.
One can compute a subtree optimal strategy on the $(u,v)$-subtree in the same
way than for the previous binary case but where the return flows are either
$r_{\sigma}(u,v)=q_{min}*|{\cal A}_{(u,v)}|$ if $\text{val}^{*}(u,v)=1$ (all
occurrences of an arc with head $u$ are placed at the end of the rotor order)
or $r_{\sigma}(u,v)=(q_{min}+1)*|{\cal A}_{(u,v)}|$ if $\text{val}^{*}(u,v)=0$
(all occurrences of an arc with head $u$ are placed at the beginning of the
rotor order). This also simplifies the integer case consequently.

  2. 2.

Let us consider the infinite set of strategies where the player can choose at
each step of the rotor walk the orientation of the vertices he controls (as in
[7]). For a vertex $v\in V_{{\cal MAX}}$, the player can choose to put the
return flow on any outgoing arc of $v$ to either $1$ or $+\infty$. Consider an
arc $(u,v)\in\hat{{\cal A}}$ and assume that $r^{*}(v,w)$ and
_$\text{val}^{*}(v,w)$_ are known for every $w\in\Gamma^{+}(v)\setminus{u}$. A
subtree optimal strategy is easily computed by choosing the strategy to always
go towards a vertex $w$ if $\text{val}^{*}(v,w)=1$ and if not to choose the
strategy that maximizes the value of $r_{\sigma}(u,v)$. In particular, if
there exists an arc $(v,u)\in\hat{{\cal A}}$ the strategy on $v$ would be to
always go towards $(v,u)$. Once again, the integer case is simplified
consequently.

##  7 Two-player Rotor Game

We now consider a two-player, zero-sum version of the zero-player game, where
players control distinct subsets of vertices of $V_{0}$, one trying to
maximize the value of the sink that has been reached whereas the other one
tries to minimize it. A similar game (but where players freely decide the
orientation of their vertices at each time step) has been studied in [18] and
shown to be P-SPACE complete.

More formally, a two-player rotor game is given by

$G=(V_{r},V_{{\cal MAX}},V_{{\cal MIN}},S_{0},{\cal
A},h,t,\theta,\text{val},\rho)$

where $V_{r},V_{{\cal MAX}},V_{{\cal MIN}}$ and $S_{0}$ are disjoint sets of
vertices, such that:

  * •

for all partial configurations $\tau$ on $V_{{\cal MIN}}$,

$G(\cdot,\tau)=(V_{r}\cup V_{{\cal MIN}},V_{{\cal MAX}},S_{0},{\cal
A},h,t,\theta,\text{val},(\rho,\tau))$

is a one-player rotor game;

  * •

for all partial configurations $\sigma$ on $V_{{\cal MAX}}$,

$G(\sigma,\cdot)=(V_{r}\cup V_{{\cal MAX}},V_{{\cal MIN}},S_{0},{\cal
A},h,t,\theta,\text{val},(\rho,\sigma))$

is a one-player rotor game.

If all the one-player games are tree-like (in other words, if the underlying
graph is tree-like) then the two-player game is also said to be tree-like.

A strategy for player ${\cal MAX}$ (respectively player ${\cal MIN}$) is a
partial rotor configuration on $V_{{\cal MAX}}$ (respectively on $V_{{\cal
MIN}}$). We denote by $\Sigma_{{\cal MAX}}$ and $\Sigma_{{\cal MIN}}$ the sets
of strategies for these players. When $\tau$ is fixed, ${\cal MAX}$ tries to
maximize the value of the final sink in $G(\cdot,\tau)$; whereas when $\sigma$
is fixed, ${\cal MIN}$ tries to minimize it in $G(\sigma,\cdot)$.

The value of the game for strategies $\sigma,\tau$ and starting vertex $u_{0}$
is denoted by $\text{val}_{\sigma,\tau}(u_{0})$ and is the value
$\text{val}(s)$ where $s$ is the sink reached by a maximal rotor walk from the
rotor particle configuration $((\rho,\sigma,\tau),u_{0})$ if any, or $0$
otherwise. As we did for one-player, we assume in the following that all rotor
games are tree-like and stopping.

When $u_{0}$ and $\rho$ are fixed, this defines a zero-sum game where ${\cal
MAX}$ and ${\cal MIN}$ try respectively to maximize and minimize the value of
the game by choosing an appropriate strategy, respectively in $\Sigma_{{\cal
MAX}}$ and $\Sigma_{{\cal MIN}}$. Usually, such a zero-sum game does not
always have an equilibrium in pure strategies and so-called mixed (i.e.
stochastic) strategies are required; this is the case in the example of Figure
13 where the given graph is not tree-like. However, in the case of tree-like
multigraphs we prove the following theorem.

######  Theorem 7.1 (Existence of pure strategy Equilibrium).

Let $G$ be a tree-like two-player rotor game together with a starting vertex
$u_{0}$. Then there are an integer value $\text{val}^{*}$ and two strategies
$\sigma^{*},\tau^{*}$ such that

  1. (i)

$\forall\tau\in\Sigma_{{\cal MIN}},\
\text{val}_{\sigma^{*},\tau}(u_{0})\geq\text{val}^{*}$, _i.e._ $\tau^{*}$ is
optimal in the one-player game $G(\sigma^{*},\cdot)$,

  2. (ii)

$\forall\sigma\in\Sigma_{{\cal MAX}},\
\text{val}_{\sigma,\tau^{*}}(u_{0})\leq\text{val}^{*}$, _i.e._ $\sigma^{*}$ is
optimal in the one-player game $G(\cdot,\tau^{*})$.

We call $\text{val}^{*}$ the value of the game and the pair
$(\sigma^{*},\tau^{*})$ is a pure strategy equilibrium.

Furthermore $\text{val}^{*}$ can be computed in the same time complexity as
the computation of $D(\rho)$ in the zero-player game (see Theorem 5.5).

This theorem is proved by following the same scheme as for the one player
game: first, we consider the binary case, and then the general case follows by
dichotomy. A constructive proof is given in both cases.

$Max$$e$$c$$1$ $d$$f$$Min$$0$ $1$ Figure 13: This example is a simple
undirected graph where each edge is replaced by two arcs. We have $V_{{\cal
MAX}}=\\{Max\\}$, $V_{{\cal MIN}}=\\{Min\\}$ and $V_{r}=\\{c,d,e,f\\}$ and
$S_{0}$ is the rest of the vertices with their value written inside them. The
particle starts on the vertex $Max$. In this game, the only optimal strategy
for ${\cal MAX}$ when the strategy for ${\cal MIN}$ is the arc $(Min,x)$ with
$x\in\\{c,d\\}$ is $(Max,x)$. On the other hand the only optimal strategy for
${\cal MIN}$ when the strategy for ${\cal MAX}$ is the arc $(Max,c)$ (resp.
$(Max,d)$) is $(Min,d)$ (resp. $(Min,c)$). The situation is like the classical
matching pennies game (see [15] for precise definition) where one player tries
to match the strategy of the opponent whereas the other player has the
opposite objective. It is known that such game does not admit a Nash
equilibrium in pure strategies.

###  7.1 Two-player Binary Rotor Game

In this subsection, we restrict the game to the case where values of sinks are
binary numbers i.e. $\text{val}(s)\in\\{0,1\\}$ for all $s\in S_{0}$.

######  Definition 7.2 (Subtree equilibrium).

A pair of strategies $\sigma^{*},\tau^{*}$ is a _subtree equilibrium_ at
$u_{0}$ if $\sigma^{*}$ (resp. $\tau^{*}$) is subtree optimal at $u_{0}$ in
the one-player game $G(\cdot,\tau^{*})$ (resp. $G(\sigma^{*},\cdot)$).

######  Lemma 7.3.

For any $(u,v)\in\hat{{\cal A}}$ and $u_{0}\in V$, there is a subtree
equilibrium at $u_{0}$ for the two-player game on $T_{(u,v)}$.

######  Proof 7.4.

This is showed by induction.

This is clearly true if $v\in S_{0}$.

Otherwise, let $(u,v)\in\hat{{\cal A}}$. Assume that there is a subtree
equilibrium $(\sigma^{*}_{w},\tau^{*}_{w})$ for every $(v,w)$-subtree with
$w\in\Gamma^{+}(v)\backslash\\{u\\}$. Consider the pairs of strategies
$\sigma_{v},\tau_{v}$ defined on $T_{(u,v)}$ such that
$\sigma_{v}(z)=\sigma^{*}_{w}(z)$ if $z\neq v$ and $z\in T_{(v,w)}$ and
$\tau_{v}(z)=\tau^{*}_{w}(z)$ if $z\neq v$ and $z\in T_{(v,w)}$.

Using 6.6:

  * •

if $v\in V_{r}$ then $\sigma_{v}$ (resp. $\tau_{v}$) is subtree optimal in
$T_{(u,v)}(\cdot,\tau_{v})$ (resp. $T_{(u,v)}(\sigma_{v},\cdot)$);

  * •

if $v\in V_{{\cal MAX}}$ then we choose $\sigma_{v}(v)$ as in 6.6 so that
$\sigma_{v}$ is subtree optimal in $T_{u,v}(\cdot,\tau_{v})$; on the other
side $\tau_{v}$ remains subtree optimal in $T_{u,v}(\sigma_{v},\cdot)$;

  * •

we proceed similarly if $v\in V_{{\cal MIN}}$.

This proves the existence of pure strategy Equilibrium as stated in Theorem
7.1. Using a minimax-like algorithm, we get the time complexity claimed in the
theorem.

###  7.2 Two-player Integer Rotor Game

By analogy with the one-player case, we can search the value of the game
$\text{val}^{*}$ in a dichotomic way. Recall that it is defined as the maximal
value that player ${\cal MAX}$ can guarantee against any strategy of ${\cal
MIN}$. To know if ${\cal MAX}$ can guarantee at least value $x$, it suffices
to solve the binary game obtained by replacing all values of sinks greater or
equal than $x$ by $1$ and the other by $0$. Then, the value of the binary game
is $1$ if and only if the value of the initial game is at least $x$. By
iterating this, $\text{val}^{*}$ can be determined by solving
$O(\log(|S_{0}|))$ binary games.

Once $\text{val}^{*}$ is known, we found no simple process to deduce an
equilibrium from the value of the game: this remains an open problem.

##  8 Simple Graph

In this section we consider simple graphs i.e. graphs such that for each
vertex $u\in V$ there is at most on arc with head $v$ when $v\in\hat{{\cal
A}}^{+}(u)$. We show specific results for this kind of graphs: firstly we give
a formula allowing to propagate the return flow without using the routine and
then we show that this helps to efficiently solve the decisional framework
when values are not restricted to be binary.

We introduce some notations that will be useful in the rest of this section.
Consider two arcs $b,c$ of $\hat{{\cal A}}^{+}(u)$, in order to measure which
one is reached first by successive rotor order operations starting on a
particular arc $a\in\hat{{\cal A}}^{+}(u)$ we define the _distance in a rotor
orbit_.

######  Definition 8.1 (Distance in a rotor orbit).

Given a vertex $u$ and $a,b\in\hat{{\cal A}}^{+}(u)$, we denote by
$d_{u}(a,b)$ the smallest $i\geq 0$ such that $\theta_{u}^{i}(a)=b$.

The following operator basically checks which arc between $b$ and $c$ is
encountered first while listing the orbit of $\theta_{u}$ starting from $a$.

######  Definition 8.2.

Let $a,b,c$ be arcs of $\hat{{\cal A}}^{+}(u)$. We define the operator $B_{u}$
such that $B_{u}(a,b,c)=1$ if $d_{u}(a,b)\leq d_{u}(a,c)$ and $B_{u}(a,b,c)=0$
if not.

###  8.1 Zero-player Game

In a simple graph, by definition $|\Gamma^{+}(u)|$ is equal to $|\hat{{\cal
A}}^{+}(u)|$. So each time that the rotor makes one full turn at vertex $u$,
the particle travels exactly once between $u$ and $v$ for each
$v\in\Gamma^{+}(u)$. Consequently, we have the following result.

######  Lemma 8.3.

If $D(\rho)(u)=(u,v)$ then all arcs $(u,w)$ of $\hat{{\cal A}}^{+}(u)$ are
visited exactly

$F_{\rho}(u,w)=r_{\rho}(u,v)\mathrel{-}B_{u}(\rho(u),(u,v),(u,w))$

times during a maximal rotor walk starting from $(\rho,u)$.

This allows to compute $D(\rho)(u)$ from the return flows of the outgoing arcs
of $u$, as stated in next lemma.

######  Lemma 8.4.

Among all arcs of $\hat{{\cal A}}^{+}(u)$ which have a minimal return flow,
the arc $D(\rho)(u)$ is the first one with respect to order $\theta_{u}$
starting at $\rho(u)$. The flow on all arcs $(u,v)\in\hat{{\cal A}}$ can be
computed in time $O(|\Gamma^{+}(u)|)$.

######  Proof 8.5.

Assume that $D(\rho)(u)=(u,v)$. From 8.3, all arcs $(u,w)$ are visited exactly
$F_{\rho}(u,w)=r_{\rho}(u,v)\mathrel{-}B_{u}(\rho(u),(u,v),(u,w))$ times
during the maximal rotor walk starting from $(\rho,u)$. Note that, for all
$w\in\Gamma^{+}(u)$, $B_{u}(\rho(u),(u,v),(u,w))$ can be computed in time
$O(|\Gamma^{+}(u)|)$ by applying $\theta_{u}$ successively starting from
$\rho(u)$.

Then, for all $w\in\Gamma^{+}(u)\setminus{v}$, we have:

$r_{\rho}(u,w)>F_{\rho}(u,w)=r_{\rho}(u,v)\mathrel{-}B_{u}(\rho(u),(u,v),(u,w))\geq
r_{\rho}(u,v)-1$

where the first inequality comes from 4.13. This gives
$r_{\rho}(u,v)<1+r_{\rho}(u,w)$, or, equivalently, $r_{\rho}(u,v)\leq
r_{\rho}(u,w)$. Hence $r_{\rho}(u,v)$ is minimal.

On the other side, if $r_{\rho}(u,w)=r_{\rho}(u,v)$ then
$B_{u}(\rho(u),(u,v),(u,w))=1$, which means that $(u,v)$ is the first arc with
respect to order $\theta_{u}$, starting at $\rho(u)$, among all arcs of
$\hat{{\cal A}}^{+}(u)$ with minimal return flow.

In that process, we also show the second part of the result i.e. the flow on
arc $(u,w)$ can be computed in time $O(|\Gamma^{+}(u)|)$.

Let $(u,v)\in\hat{{\cal A}}$ with $u\in V_{0}$. Consider the $(u,v)$-subtree
and let $(v,w)$ be the orientation of $v$ in the Destination Forest in that
subtree. From 8.3 we have
$r_{\rho}(u,v)=r_{\rho}(v,w)+B_{v}(\rho(v),(v,u),(v,w))$. Combining this with
8.4, we obtain the following recursive computation of $r_{\rho}(u,v)$.

$r_{\rho}(u,v)=\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r_{\rho}(v,w)+B_{v}(\rho(v),(v,u),(v,w))$
(1)

We then have a result similar to that of 5.3.

######  Lemma 8.6 (Simple Retropropagation for the Zero-player Game).

Given $v\in V$, assuming the return flows of all arcs $(v,w)$ for
$w\in\Gamma^{+}(v)$ are known, one can compute the return flow of all arcs
$(z,v)$ with $z\in\Gamma^{-}(v)$ by applying Equation (1) at most twice in
time $O(\min(|\Gamma^{+}(v)|,|\Gamma^{-}(v)|))$.

######  Proof 8.7.

For every vertex $z\in\Gamma^{-}(v)\setminus\Gamma^{+}(v)$ we set
$r_{\rho}(z,v)=1$ (or $r_{\rho}(z,v)=0$ if $z\in S_{0})$.

As the graph is stopping, there is at least one vertex $w\in\Gamma^{+}(v)$
such that the return flow of $(v,w)$ is finite. Let $(v,w_{0})=D_{\rho}(v)$ be
the first arc with respect to order $\theta_{v}$ starting from $\rho(v)$ such
that $r_{\rho}(v,w_{0})=\min_{w\in\Gamma^{+}(v)}r_{\rho}(v,w)$. Then, for any
$(w,v)$-subtree with $w\in\Gamma^{-}(v)$ and $w\neq w_{0}$, the last outgoing
arc of $v$ when routing a particle from $(\rho,v)$ is $(v,w_{0})$, hence by
Equation (1), we have
$r_{\rho}(w,v)=r_{\rho}(v,w_{0})+B_{v}(\rho(v),(v,w),(v,w_{0}))$. Note that
all values $B_{v}(\rho(v),(v,w),(v,w_{0}))$ can be computed in time
$O(|\Gamma^{+}(v)|)$ by iterating $\theta_{v}$ from $\rho(v)$. It remains to
compute $r_{\rho}(w_{0},v)$ which can be done by applying Equation (1) once
more. Potentially, the return flows of all arcs $(v,w)$ with
$w\in\Gamma^{+}(v)\setminus\\{w_{0}\\}$ might be infinite. In that case, we
have $r_{\rho}(w_{0},v)=+\infty$.

From, here, we have all the tools to construct our recursive algorithm.

######  Theorem 8.8 (Complete Destination Algorithm for simple graphs).

The configuration $D(\rho)$ can be computed in time complexity $O(|{\cal
V}|)$.

######  Proof 8.9.

We use the same algorithm as for the multigraph case (see Theorem 5.5), except
that we replace routine IRR used for propagating the return flow by Equation
(1), which is more efficient since it does not need a division. And 5.3 is
replaced by 8.6. Since the graph is simple, we have $|\hat{{\cal A}}|=|{\cal
A}|=O(|{\cal V}|)$ hence the result.

###  8.2 One-player Simple Tree-like Rotor Game

We now consider one-player rotor games when the graph is simple. For a simple
tree-like rotor game, with binary values, we show that we can compute the
optimal value of every starting vertex in the same time than in Theorem 8.8.
Then, contrary to the case presented subsection 6.2, for a simple game with
integer values, we can achieve linear complexity to compute the value of the
game.

First, 8.10 is a direct consequence of 8.4. It characterizes a subset of arcs
likely to be the last outgoing arc of $v$.

######  Lemma 8.10.

Consider a one-player simple tree-like rotor game $G$, a vertex $u\in V_{0}$
and a strategy $\sigma$. Then, we have
$h(D(\rho,\sigma)(u))\in\text{argmin}_{v\in\Gamma^{+}(u)}r_{\sigma}(u,v)$.

This is true in particular for an optimal strategy of the one-player simple
tree-like rotor game. Thus, we can propagate the values and return flows more
easily than for the one-player tree-like rotor game.

####  8.2.1 Binary Values

Consider a one-player simple tree-like rotor game with binary values and a
strategy $\sigma$ for the player.

######  Lemma 8.11 (Optimal Values and Return Flows).

Let $(u,v)\in\hat{{\cal A}}$. Then:

  1. 1.

If $v\in V_{r}$, suppose that we know all optimal values $\text{val}^{*}(v,w)$
and optimal return flows $r^{*}(v,w)$ of all arcs $(v,w)$ with $w\neq u$. From
this we can compute $\text{val}^{*}(u,v)$ and $r^{*}(u,v)$ by:

$\text{val}^{*}(u,v)=\text{val}^{*}(v,w_{f})\text{ and
}r^{*}(u,v)=r^{*}(v,w_{f})+B_{v}(\rho(v),(v,u),(v,w_{f}))$

where $w_{f}=h(D(\rho,\sigma)(v))$, i.e. $(v,w_{f})$ is the last outgoing arc
of $v$.

  2. 2.

If $v\in V_{{\cal MAX}}$ and if there is at least one arc $(v,w_{1})$ with
$w_{1}\in\Gamma^{+}(v)\setminus\\{u\\}$ such that $\text{val}^{*}(v,w_{1})=1$
and $r^{*}(v,w_{1})=\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r^{*}(v,w)$ then,

$\text{val}^{*}(u,v)=1\text{ and
}r^{*}(u,v)=\left\\{\begin{array}[]{ll}r^{*}(v,w_{1})\text{ if
}(v,u)\in\hat{{\cal A}};\\\ 1\text{ if not}.\end{array}\right.$

  3. 3.

If $v\in V_{{\cal MAX}}$ and if there is no arc $(v,w_{1})$ as in case 2, we
have

$\text{val}^{*}(u,v)=0\text{ and
}r^{*}(u,v)=\left\\{\begin{array}[]{ll}1+\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r^{*}(v,w)\text{
if }(v,u)\in\hat{{\cal A}};\\\ 1\text{ if not}.\end{array}\right.$

Note that $r^{*}(u,v)$ can be infinite.

######  Proof 8.12.

  1. 1.

If $v\in V_{r}$, we use Equation (1).

  2. 2.

Let $(v,w_{1})$ be an arc with $w_{1}\in\Gamma^{+}(v)\setminus\\{u\\}$ such
that $\text{val}^{*}(v,w_{1})=1$ and
$r^{*}(v,w_{1})=\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r^{*}(v,w)$. 8.3
implies that there is a strategy $\sigma$ with $D(\rho,\sigma)=(v,w_{1})$,
hence $\text{val}^{*}(u,v)=1$. Furthermore, given any strategy $\sigma$ such
that $\text{val}_{\sigma}(u,v)=1$, and for all $w$ such that
$\text{val}^{*}(v,w)=1$ we have $r_{\sigma}(v,w)\geq r^{*}(v,w)\geq
r^{*}(v,w_{1})$, hence $r^{*}(u,v)=r^{*}(v,w_{1})$.

  3. 3.

Otherwise, all arcs with minimal return flows have optimal value $0$.
Obviously, this implies $\text{val}^{*}(u,v)=0$. Given any strategy $\sigma$,
for all $w$ such that $\text{val}^{*}(v,w)=0$, we have $r^{*}(v,w)\geq
r_{\sigma}(v,w)$ hence
$\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r^{*}(v,w)\geq\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r_{\sigma}(v,w)$.
Furthermore, if $(v,u)\in\hat{{\cal A}}$, there is a strategy (namely choosing
$(v,u)$ as the starting configuration of $v$) such that $(v,u)$ is visited
$\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r^{*}(v,w)+1$ times. Hence, we have
$r^{*}(u,v)=1+\min_{w\in\Gamma^{+}(v)\setminus\\{u\\}}r^{*}(v,w)$.

By analogy with 6.6, we can construct a recursive linear algorithm to compute
the optimal value of $u_{0}$. But, contrary to the one-player tree-like rotor
game on multigraphs, as the graph is simple, we can also compute in linear
time the return flows and values of all arcs of $\hat{{\cal A}}$ that are not
directed from $u_{0}$ towards the leaves. The reason we should do this is
that, if we know all return flows of all arcs, in the end we can compute
optimal values and strategies for all starting vertices simultaneously.
Indeed, by using conjointly 8.6 and 8.11 this can be done in at most $2|{\cal
A}^{+}(u)|$ steps for a given vertex $u$. This result is properly stated in
the following Lemma.

######  Lemma 8.13 (Optimal Retropropagation).

Given a vertex $v\in V$ and assuming the return flows and values of all arcs
$(v,w)$ for $w\in\Gamma^{+}(v)$ are known, one can compute all optimal return
flows and all optimal values of arcs $(u,v)$ with $u\in\Gamma^{-}(v)$ by
applying at most twice Equation (1).

######  Proof 8.14.

If $v\in V_{r}$, this is exactly 8.6 concerning the zero-player case. So we
focus on the case where $v\in V_{{\cal MAX}}$.

Let $\Gamma_{\min}^{+}(v)\subset\Gamma^{+}(v)$ be the set of $w$ in
$\text{argmin}_{w\in\Gamma^{+}(v)}r^{*}(v,w)$. From 8.10, we have that, no
matter the strategy $\sigma$ chosen on $v$,
$h(D(\rho,\sigma)(v))\in\Gamma_{\min}^{+}(v)$. From here we distinct two
cases.

  * •

Either there is a vertex $w_{1}\in\Gamma_{\min}^{+}(v)$ such that
$\text{val}^{*}(v,w_{1})=1$ (there might be several such vertices). In this
case, 8.11 (case 2) states that for all arcs $(u,v)$ with $u\neq w_{1}$ we
have $\text{val}^{*}(u,v)=1$ and $r^{*}(u,v)=r^{*}(v,w_{1})$ if there is an
arc $(v,u)$ and $r^{*}(u,v)=1$ if not. If $(w_{1},v)\in\hat{{\cal A}}$, it
remains to consider the case of $(w_{1},v)$, which can be done by applying a
second time 8.11 (case 2) with $u=w_{1}$.

  * •

If there is no such vertex $w_{1}\in\Gamma_{\min}^{+}(v)$ such that
$\text{val}^{*}(v,w_{1})=1$, choose any vertex $w_{0}\in\Gamma_{\min}^{+}(v)$.
By using 8.11 (case 3) for all arcs $(u,v)$ with $u\neq w_{0}$ we have that
$\text{val}^{*}(u,v)=0$ and $r^{*}(u,v)=r^{*}(v,w_{0})+1$ if there is an arc
$(v,u)$, and $r^{*}(u,v)=1$ if not. As for the previous case, if
$(w_{0},v)\in\hat{{\cal A}}$, it remains to consider the case of $(w_{0},v)$,
which can be done by applying a second time 8.11 (case 3) with $u=w_{0}$.

This allows us to compute the optimal values of all vertices in linear time.

######  Theorem 8.15.

Given a one-player binary tree-like rotor game on a simple graph, we can
compute the optimal values of all vertices in time complexity $O(|V|)$.

######  Proof 8.16.

We consider the arcs in the same order than in Theorem 5.5. For all arcs
directed from $u_{0}$ towards the leaves, we use 8.11. This is done in
$O(|\hat{{\cal A}}|)$ comparisons. Then, for all arcs directed from the leaves
towards $u_{0}$ we use 8.13 which is done in $O(|\hat{{\cal A}}|)$
comparisons. Then, we just need to compute the optimal value of each vertex as
in the proof of Theorem 6.8. Which is done in $O(|{\cal A}|)$ comparisons as
well.

######  Remark 8.17.

This procedure gives us the optimal value of the game simultaneously for every
starting vertex, in overall linear time. However, as noted before (see Figure
10), the optimal strategy depends on the starting vertex.

This extension is also valid for the two-player binary variant on a simple
graph as the subtree optimal equilibrium is preserved for the same reason than
in subsection 7.1.

####  8.2.2 One-player Simple Integer Rotor Game

This last subsection introduces a notion of _access flow_ that measures the
potential access to an arc for a rotor walk starting at $u_{0}$. It allows us
to compute the optimal value of the game in linear time for the integer case
on a simple graph, in contrast to the general case where we had to use a
bisection algorithm (subsection 6.2).

######  Lemma 8.18 (Strategy $\sigma_{max}$).

Given a vertex $u_{0}$, there is a strategy $\sigma_{max}\in\Sigma_{{\cal
MAX}}$ such that, for all arc $(u_{0},v)\in\hat{{\cal A}}$,

$r_{\sigma_{max}}(u_{0},v)=\max_{\sigma\in\Sigma_{{\cal
MAX}}}r_{\sigma}(u_{0},v),$

namely any strategy that chooses to direct arcs towards $u_{0}$ when possible.

######  Proof 8.19.

We prove recursively that the strategy $\sigma_{max}$ described above is
maximal, starting from leaves and going back to $u_{0}$. Let
$(u,v)\in\hat{{\cal A}}$ such that $(u,v)$ is directed towards the leaves,
suppose that all return flows of arcs $(v,w)\in\hat{{\cal A}}$ with
$w\in\Gamma^{+}(v)\setminus\\{u\\}$ are maximal. If $v\in V_{r}$,
$r_{\sigma}(u,v)$ is maximal if the return flow of $D(\rho,\sigma)(v)$ is
maximal among all strategies $\sigma$. By choosing $\sigma_{max}(v)=(v,u)$, we
have $B_{v}(\sigma(v),(v,u),(v,w))=1$ for any
$w\in\Gamma^{+}(v)\setminus\\{u\\}$. At the same time, $\sigma(v)$ is directed
towards $u_{0}$. From Equation (1), we then have that, no matter the value of
the return flow of the arcs $(v,w)$, as long as it is maximal, the return flow
of $(u,v)$ is maximal. If there is no arc $(v,u)$, the choice does not matter
as $r_{\sigma}(u,v)=1$ for any strategy $\sigma\in\Sigma_{{\cal MAX}}$.

######  Definition 8.20 (Access flow $\text{acc}(u,v)$).

For every arc $(u,v)\in\hat{{\cal A}}$, we denote by $\text{acc}(u,v)$ the
value such that, if we remove all outgoing arcs of $v$ and we add an arc
$(v,u)$, $\text{acc}(u,v)$ is the maximal number of times arc $(u,v)$ is
visited in the maximal rotor walk starting from $((\rho,\sigma),u_{0})$ for
all strategies $\sigma\in\Sigma_{{\cal MAX}}$. Note that $\text{acc}(u,v)$
might be infinite in the case where all sinks are in $T_{(u,v)}$.

In particular, $\text{acc}(u,v)$ is positive if and only if there exists a
strategy $\sigma$ such that $v$ is visited at least once in the maximal rotor
walk starting from $((\rho,\sigma),u_{0})$.

A sink $s$ is said to be _reachable_ if, for $(u,s)\in\hat{{\cal A}}$,
$\text{acc}(u,s)$ is positive. Hence, to solve our problem we just need to
find the sink $s_{\max}$ of maximal value among the reachable sinks.

From here we present the linear process that allows to compute the access flow
of all arcs with head in $S_{0}$.

######  Lemma 8.21 (Access flow around $u_{0}$).

Let $\sigma_{\text{max}}$ be the strategy detailed above. For any
$v_{i}\in\Gamma^{+}(u_{0})$ we have:

$\text{acc}(u_{0},v_{i})=\left\\{\begin{array}[]{ll}\min_{v_{j},j\neq
i}r_{\sigma_{\text{max}}}(u_{0},v_{j})-B_{u_{0}}(\rho(u_{0}),(u_{0},v_{j}),(u_{0},v_{i}))&\text{
if }u_{0}\in V_{r}\\\ \min_{v_{j},j\neq
i}r_{\sigma_{\text{max}}}(v_{0},v_{j})&\text{ if }u_{0}\in V_{{\cal MAX}}\\\
\end{array}\right.$

######  Proof 8.22.

To maximize the number of times $(u_{0},v_{i})$ is visited in the definition
of $\text{acc}(u_{0},v_{i})$, we need to maximize the return flows of all arcs
$(u_{0},v_{j})$. All these arcs are directed from $u_{0}$ towards leaves, so
the return flow of these arcs under strategy $\sigma_{max}$ is maximum among
all strategies. Both cases derive from Equation (1), but in the second one,
$u_{0}$ is initially directed towards $v_{i}$.

Similarly to the return flow, we give a recursive equation that computes the
access flow on all arcs directed from $u_{0}$ towards the leaves.

######  Lemma 8.23 (Access flow Propagation).

Let $(u,v)\in\hat{{\cal A}}$, let $w_{0},..,w_{k}$ be the vertices of
$\Gamma^{+}(v)\setminus u$. If we know $\text{acc}(u,v)$, then, for any couple
$(v,w_{i})$ we have:

$\text{acc}(v,w_{i})=\min\left\\{\begin{array}[]{ll}\min_{w_{j},j\neq
i}r_{\sigma_{max}}(v,w_{j})-B_{v}(\rho(v),(v,w_{j}),(v,w_{i}));\\\
\text{acc}(u,v)-B_{v}(\rho(v),(v,u),(v,w_{i}))\end{array}\right.$

If $v\in V_{{\cal MAX}}$, we have:

$\text{acc}(v,w_{i})=\min\left\\{\begin{array}[]{ll}\min_{w_{j},j\neq
i}r_{\sigma_{max}}(v,w_{j});\\\ \text{acc}(u,v)\end{array}\right.$

as the player can always choose $\sigma(v)=(v,w_{i})$.

Once again, using this formula to compute all access flows might take more
than a linear time, so we give a property similar to 8.6 allowing to compute
all access flows in linear time.

######  Lemma 8.24 (Access flow Computation).

Let $(u,v)\in\hat{{\cal A}}$ and $w_{0},..,w_{k}$ be the vertices of
$\Gamma^{+}(v)\setminus u$, and assume that $\text{acc}(u,v)$ is known. Then
$\text{acc}(v,w_{i})$ can be determined for all $i\in\\{0\dots k\\}$ by
computing $\text{acc}(v,w_{i})$ for only two values of $i$.

######  Proof 8.25.

Same proof than for 8.6 if vertex $v$ belongs to $V_{r}$. If $v\in V_{{\cal
MAX}}$, we also use 8.6 but with $B_{v}(\sigma(v),(v,u),(v,w_{i}))=0$ for all
$w_{i}\in\Gamma^{+}(v)\setminus\\{u\\}$.

######  Theorem 8.26.

One can compute the value of a one-player tree-like rotor game with arbitrary
integer values in linear time $O(|V|)$ for a given starting vertex $u_{0}$.

######  Proof 8.27.

Consider the arcs in the same order than in Theorem 5.5. For all arcs directed
from $u_{0}$ towards the leaves, we compute the maximal return flows
recursively from the leaves (i.e. constructing strategy $\sigma_{max}$). Then,
for all arcs with tail $u_{0}$ we use 8.21 and finally we use 8.24 to compute
the access flow on all arcs directed towards the leaves. Each arc is
considered at most twice so the complexity of these steps sums up to
$O(|\hat{{\cal A}}|)$. After that, the value of the game is the reachable sink
with maximal value which is computed in $O(|V|)$. As the graph is tree-like
and simple we have $|\hat{{\cal A}}|\leq 2|V|$ hence our complexity result.

As a concluding example, let us apply this Theorem to the example of Figure 14
to compute the correct value of the game.

$u_{0}$$v$$0$ $1$ $2$ Figure 14: Example of a simple integer tree-like rotor
game. Here, $v\in V_{{\cal MAX}}$ and $u_{0}\in V_{r}$. All other vertices
belong to $S_{0}$ and their value is written inside them. The initial
configuration of $u_{0}$ is the red arc in dashes.

First, compute the return flows of arcs $(u_{0},2)$ and $(u_{0},v)$ under
strategy $\sigma_{\max}$. We have $r_{\sigma_{\max}}(u_{0},2)=1$ and
$r_{\sigma_{\max}}(u_{0},v)=2$. From 8.21, we have $\text{acc}(u_{0},2)=1$ as
$B_{u_{0}}(\rho(u_{0}),(u_{0},v),(u_{0},2))=1$. From the same formula we have
$\text{acc}(u_{0},v)=1$. And by 8.24 we have
$\text{acc}(v,1)=\text{acc}(v,0)=1$. All sinks are reachable, and $2$ is the
maximal value among them, hence $\text{val}^{*}(v_{0})=2$.

## Future Work

Concerning ARRIVAL, one remaining fundamental question is to determine whether
there exists a polynomial algorithm to solve the zero-player game. Similarly,
problems such as _simple stochastic games, parity games_ and _mean-payoff
games_ are also in NP $\cap$ co-NP, and there are no polynomial algorithm
known to solve them (see [12]). For those different problems, considering sub-
classes of graphs where we can find polynomial algorithms is a fruitful
approach (see [1] and [2]). This paper is a first step in this direction.

Thus, we would like to study more general classes of graphs. To begin with,
even graphs that are well-studied in terms of the _sandpile group_ such that
ladders or grids remain now an open problem for ARRIVAL. The problem of
finding the destination of multiple particles at the same time is also an
important open problems in nearly all cases except the path graph.

Finally, another natural extension of our algorithm would be to define and
study an adequate notion of graphs with bounded width to generalize the Tree-
like multigraph case.

### Acknowledgment

## References

  * [1] David Auger, Pierre Coucheney, and Yann Strozecki.  Finding optimal strategies of almost acyclic simple stochastic games.  In International Conference on Theory and Applications of Models of Computation, pages 67–85. Springer, 2014.
  * [2] David Auger, Pierre Coucheney, and Yann Strozecki.  Solving simple stochastic games with few random nodes faster using bland’s rule.  In 36th International Symposium on Theoretical Aspects of Computer Science, 2019.
  * [3] Anders Björner, László Lovász, and Peter W Shor.  Chip-firing games on graphs.  European Journal of Combinatorics, 12(4):283–291, 1991.
  * [4] Richard P Brent and Paul Zimmermann.  Modern computer arithmetic, volume 18.  Cambridge University Press, 2010.
  * [5] Swee Hong Chan, Lila Greco, Lionel Levine, and Peter Li.  Random walks with local memory.  Journal of Statistical Physics, 184(1):1–28, 2021.
  * [6] Joshua N Cooper and Joel Spencer.  Simulating a random walk with constant error.  Combinatorics, Probability and Computing, 15(6):815–822, 2006.
  * [7] Jérôme Dohrau, Bernd Gärtner, Manuel Kohler, Jiří Matoušek, and Emo Welzl.  Arrival: A zero-player graph game in NP $\cap$ coNP.  In A journey through discrete mathematics, pages 367–374. Springer, 2017.
  * [8] Tobias Friedrich and Thomas Sauerwald.  The cover time of deterministic random walks.  In International Computing and Combinatorics Conference, pages 130–139. Springer, 2010.
  * [9] Bernd Gärtner, Thomas Dueholm Hansen, Pavel Hubácek, Karel Král, Hagar Mosaad, and Veronika Slívová.  Arrival: Next stop in cls.  In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018\.
  * [10] Bernd Gärtner, Sebastian Haslebacher, and Hung P. Hoang.  A Subexponential Algorithm for ARRIVAL.  In ICALP 2021, volume 198, pages 69:1–69:14, 2021.
  * [11] Giuliano Pezzolo Giacaglia, Lionel Levine, James Propp, and Linda Zayas-Palmer.  Local-to-global principles for rotor walk.  arXiv preprint arXiv:1107.4442, 2011.
  * [12] Nir Halman.  Simple stochastic games, parity games, mean payoff games and discounted payoff games are all LP-type problems.  Algorithmica, 49(1):37–50, 2007.
  * [13] David Harvey and Joris Van Der Hoeven.  Integer multiplication in time O(n log n).  Annals of Mathematics, 193(2):563–617, 2021.
  * [14] Alexander E. Holroyd, Lionel Levine, Karola Mészáros, Yuyal Peres, James Propp, and David B. Wilson.  Chip-Firing and Rotor-Routing on Directed Graphs, pages 331–364.  Springer, 2008.
  * [15] Martin J Osborne.  Introduction to Game Theory.  Oxford University Press, 2004.
  * [16] AM Povolotsky, VB Priezzhev, and RR Shcherbakov.  Dynamics of eulerian walkers.  Physical review E, 58(5):5449, 1998.
  * [17] Vyatcheslav B Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy.  Eulerian walkers as a model of self-organized criticality.  Physical Review Letters, 77(25):5079, 1996.
  * [18] Rahul Savani, Matthias Mnich, Martin Gairing, and John Fearnley.  Reachability switching games.  Logical Methods in Computer Science, 17, 2021.
  * [19] Vladimir Yanovski, Israel A Wagner, and Alfred M Bruckstein.  A distributed ant algorithm for protect efficiently patrolling a network.  Algorithmica, 37(3):165–186, 2003.