# Tree exploration in dual-memory model

Dominik Bojko  Wrocław University of Science and Technology, Poland,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Karol Gotfryd  Wrocław University of Science and Technology, Poland,
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Dariusz R. Kowalski  School of Computer and Cyber Sciences, Augusta
University, USA<EMAIL_ADDRESS>Dominik Pajak  Wrocław University of
Science and Technology, Poland<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

We study the problem of online tree exploration by a deterministic mobile
agent. Our main objective is to establish what features of the model of the
mobile agent and the environment allow linear exploration time. We study
agents that, upon entering to a node, do not receive as input the edge via
which they entered. In such a model, deterministic memoryless exploration is
infeasible, hence the agent needs to be allowed to use some memory. The memory
can be located at the agent or at each node. The existing lower bounds show
that if the memory is either only at the agent or only at the nodes, then the
exploration needs superlinear time. We show that tree exploration in dual-
memory model, with constant memory at the agent and logarithmic at each node
is possible in linear time when one of two additional features is present:
fixed initial state of the memory at each node (so called clean memory) or a
single movable token. We present two algorithms working in linear time for
arbitrary trees in these two models. On the other hand, in our lower bound we
show that if the agent has a single bit of memory and one bit is present at
each node, then exploration may require quadratic time on paths, if the
initial memory at nodes could be set arbitrarily (so called dirty memory).
This shows that having clean node memory or a token allows linear exploration
of trees in the model with two types of memory, but having neither of those
features may lead to quadratic exploration time even on a simple path.

##  1 Introduction

Consider a mobile entity deployed inside an undirected graph with the
objective to visit all its nodes and traverse all its edges, without any a
priori knowledge of the topology of the graph or of its size. This problem,
called a graph exploration, is among the basic problems investigated in the
context of a mobile agent in a graph. In this paper we focus on tree
exploration by a deterministic agent. Clearly, to explore the whole tree of
$n$ nodes, any agent needs time $\Omega(n)$. A question arises: ’’What are the
minimum agent capabilities for it to be able to complete the tree exploration
in linear time?‘‘ Many practical applications may not allow the agent to
easily backtrack its moves, due to technical, security or privacy reasons –
hence, in this work we assume that the agent, upon entering a node, does not
receive any information about the edge via which it entered.

A deterministic agent at a node of degree $d$ needs at least $d$ different
inputs in order to be able to choose any of $d$ outgoing edges. We consider
three components of the input to the agent: memory at the agent, memory at
each node, and movable tokens. In order to ensure the sufficient number of
possible inputs, the number of possible values of the memory and possible
present or absent states of the tokens, must exceed $d$. Hence, the sum of the
memory at the agent, memory at the node and the total number of tokens must be
at least $\lceil\log d_{v}\rceil$ bits, for any node of degree $d_{v}$ (we
denote by $\log$ the base-$2$ logarithm).

In many applications, mobile agents are meant to be small, simple and
inexpensive devices or software. These restrictions limit the size of the
memory with which they can be equipped. Thus it is crucial to analyze the
performance of the agent equipped with the minimum size of the memory. In this
paper we assume the asymptotically minimum necessary memory size of $O(\log
d_{v})$, where only a constant number of bits is stored at the agent and
logarithmic number at each node. Our result in the model with the tokens
assumes the presence of only a single movable token.

The main focus of the paper is on deterministic tree exploration in the
minimum possible time using the minimum possible memory. We consider two
additional features of the model, namely – clean memory or a token, and we
show that each of these assumptions alone allows linear time tree exploration.
We also prove that when both features are absent, then the linear time
exploration with small memory may be impossible even on a simple path.

##  2 Model

The agent is located in an initially unknown tree $T=(V,E)$ with $n=|V|$
nodes. The agent can traverse one of the edges incident to its current
location within a single step, in order to visit a neighboring node at its
other end. The nodes of the tree are unlabelled, however in order for the
agent to locally distinguish the edges outgoing from its current position, we
assume that the tree is port-labelled. This means that at each node $v$ with
some degree $d_{v}$, its outgoing edges are uniquely labelled with numbers
from $\\{1,2,\dots,d_{v}\\}$. Throughout the paper we assume that the port
labels are assigned by an adversary that knows the algorithm used by the agent
and wants to maximize the exploration time.
Memory. The agent is endowed with some number of memory bits (called _agent
memory_ or _internal memory_), which it can access and modify. In our results,
we assume that the agent has $O(1)$ bits of memory, hence a constant number of
states.

Each node $v\in V$ contains some number of memory bits that can be modified by
the agent when visiting that node. We will call these bits _node memory_ or
_local memory_. We assume that node $v$ contains $\Theta(\log d_{v})$ bits of
memory. Hence, each node can store a constant number of pointers to its
neighbors.
Algorithm. Upon entering a node $v$, the agent $a$ receives, as input, its
current state $S_{a}$, the state $S_{v}$ of the current node $v$, the number
$T_{v}$ of tokens at $v$, the number $T_{a}$ of tokens at the agent and the
degree $d_{v}$ of the current node. It outputs its new state $S^{\prime}_{a}$,
new state $S^{\prime}_{v}$ of node $v$, new state
$T^{\prime}_{a},T^{\prime}_{v}$ of the tokens at the agent/node, respectively,
and port number $p_{out}$ via which it exits node $v$; hence, the algorithm
defines a transition:

$(S_{a},S_{v},T_{a},T_{v},d_{v})\rightarrow(S^{\prime}_{a},S^{\prime}_{v},T^{\prime}_{a},T^{\prime}_{v},p_{out})$

In models without the tokens, the state transition of the algorithm can be
simplified to:

$(S_{a},S_{v},d_{v})\rightarrow(S^{\prime}_{a},S^{\prime}_{v},p_{out})$

Starting state. We assume that for a given deterministic algorithm, there is
one starting state $s$ of the agent (obtained from the agent memory), in which
the agent is at the beginning of (any execution of) the algorithm. The agent
can also use this state later (it can transition to $s$ in subsequent steps of
the algorithm). The starting location of the agent is chosen by an adversary
accordingly to agent‘s algorithm (to maximize the agent‘s exploration time).
Our models. In this paper we study the following three models:

In CleanMem, there is a fixed state $\hat{s}$ and each node $v$ is initially
in the state $S_{v}=\hat{s}$, regardless of the degree of the vertex. In this
model the agent does not have access to any tokens.

In DirtyMem, the memory at the nodes is in arbitrary initial states, which are
chosen by an adversary. In this model the agent does not have access to any
tokens.

In Token, the agent is initially equipped with a single token. If the agent
holds a token, it can drop it at a node upon visiting that node. When visiting
a node, the agent receives as input whether the current node already contains
a token. In this case the agent additionally outputs whether it decides to
pick up the token, i.e., deduct from $T_{v}$ and add to $T_{a}$. Clearly,
since the agent has only one token, then after dropping it at some node, it
needs to pick it up before dropping it again at some other node. In this model
we assume that the initial state of the memory at each node is chosen by an
adversary (like in DirtyMem model).

##  3 Our results

Upper bounds. While most of the existing literature focus on feasibility of
the exploration, we show that it is possible to complete the tree exploration
in the minimum possible linear time using (asymptotically) minimal memory. We
show two algorithms in models CleanMem and Token, exploring arbitrary unknown
trees in the optimal time $O(n)$ if constant memory is located at the agent
and logarithmic memory is located at each node. Our results show that in the
context of tree exploration in dual-memory model, the assumption about clean
memory (fixed initial state of node memory) can be ’’traded‘‘ for a single
token.

It is worth noting that in both our algorithms, the agent returns to the
starting position and terminates after completing the exploration, which is a
harder task than a perpetual exploration. If the memory is only at the agent,
exploration of trees with stop at the starting node requires $\Omega(\log n)$
bits of memory [10]; if the agent is only required to terminate at any node
then still a superconstant $\Omega(\log\log\log n)$ memory is required [10];
while exploration without stop is feasible using $O(\log\Delta)$ agent memory
[10] (where $\Delta$ is the maximum degree of a node). All these results
assume that the agent could receive the port number via which it entered the
current node, while our algorithms operate without this information.
Lower bound. To explore a path with a single bit of memory and with arbitrary
initial state at each node (note that $\log d_{v}=1$ for internal nodes on the
path), one can employ the Rotor-Router algorithm and achieve exploration time
of $O(n^{2})$ [30] (there is no need for agent memory), which is time and
memory optimal in the model with only node memory [25].

In our lower bound we analyze line exploration with one bit at each node and
additional one bit of memory at the agent. We want to verify the hypothesis
that dual-memory allows to achieve linear time of exploration. We provide a
partial argument for the contrary – we prove that in DirtyMem model an
exploration of the path requires $\Omega(n^{2})$ steps in the worst case. This
shows that adding a single bit at the agent to the model with a single bit at
each node does not reduce the exploration time significantly.

###  3.1 Previous and related work

Only node memory. One approach for graph exploration that uses only node
memory is Rotor-Router [30]. It is a simple strategy, where upon successive
visits to each node, the agent is traversing the outgoing edges in a round-
robin fashion. Its exploration time is $\Theta(mD)$ for any graph with $m$
edges and diameter $D$ [2, 30]. It is easy to see that this algorithm can be
implemented in port-labelled graphs with zero bits of memory at the agent and
only $\lceil\log d_{v}\rceil$ bits of memory at each node $v$ with degree
$d_{v}$ (note that this is the minimum possible amount of memory for any
correct exploration algorithm using only memory at the nodes). Allowing even
unbounded memory at each node still leads to $\Omega(n^{3})$ time for some
graphs, and $\Omega(n^{2})$ time for paths [25]. Interestingly, these lower
bounds hold even if the initial state of the memory at each node is clean
(i.e., each node starts in some fixed state $\hat{s}$ like in CleanMem model).
Hence, having only memory at the nodes is insufficient for exploration of
trees faster than in quadratic time.
Only agent memory. When the agent is not allowed to interact with the
environment, then such agent, when exploring regular graphs, does not acquire
any new information during exploration. Hence such an algorithm, is
practically a sequence of port numbers that can be defined prior to the
exploration process. In the model with agent memory, the agent is endowed with
some number of bits of memory that the agent can access and modify at any
step. If this number of bits is logarithmic in $n$ (otherwise, the exploration
is infeasible [10]), then in this model it is possible to implement Universal
Traversal Sequences (the agent only remembers the position in the sequence).
However, such sequences require $\Omega(n^{1.51})$ steps to explore paths [7].
Best known upper bound is $O(n^{3})$ [1] and the best known constructive upper
bound is $O(n^{4.03})$ [23]. Memory $\Theta(D\log\Delta)$ is sufficient and
sometimes required to explore any graph with maximum degree $\Delta$ [17]. For
directed graphs, memory $\Omega(n\log\Delta)$ at the agent is sometimes
required to explore any graph with maximum outdegree $\Delta$, while memory
$O(n\Delta\log\Delta)$ is always sufficient [16].
Finite state automata. An agent equipped with only constant number of bits of
persistent memory (independent of the network size and topology and other
parameters of the model) can be regarded as a finite state automaton (see e.g.
[6, 17, 18]). Movements of such agent, typically modeled as a finite Moore or
Mealy automaton, are completely determined by a state transition function
$f(s,p,d_{v})=(s^{\prime},p^{\prime})$, where $s$, $s^{\prime}$ are the
agent‘s states and $p$, $p^{\prime}$ are the ports through which the agent
enters and leaves the node $v$. A finite state automaton cannot explore an
arbitrary graph in the setting, where the nodes have no unique labels [28].
Fraigniaud et al. [17] showed that for any $\Delta\geqslant 3$ and any finite
state agent with $k$ states, one can construct a planar graph with maximum
degree $\Delta$ and at most $k+1$ nodes, that cannot be explored by the agent.
It is, however, possible in this model to explore (without stop) the trees,
assuming that the finite state agent has access to the incoming port number
(cf. [10]).
Tokens. Deterministic, directed graph exploration in polynomial time using
tokens has been considered in [4], where the authors show that a single token
is sufficient if the agent has an upper bound on the total number of vertices
and $\Theta(\log\log n)$ tokens are sufficient and necessary otherwise. In [3]
the authors proposed a probabilistic polynomial time algorithm that allows two
cooperating agents without the knowledge of $n$ to explore any strongly
connected directed graph. They also proved that for a single agent with $O(1)$
tokens this is not possible in polynomial time in $n$ with high probability.
In [18] it was shown that using one pebble, the exploration with stop requires
an agent with $\Omega(\log n)$ bits of memory. The same space bound remains
true for perpetual exploration [17].
Two types of memory. Sudo et al. [29] consider exploration of general graphs
with two types of memory. They show that $O(\log n)$ bits at the agent and at
each node allows exploration in time $O(m+nD)$. Cohen et al. [6] studied the
problem of exploring an arbitrary graph by a finite state automaton, which is
capable of assigning $O(1)$-bit labels to the nodes. They proposed an
algorithm, that – assuming the agent knows the incoming port numbers –
dynamically labels the nodes with three different labels and explores (with
stop) an arbitrary graph in time $O(mD)$ (if the graph can be labelled
offline, both the preprocessing stage and the exploration take $O(m)$ steps).
They also show that with $1$-bit labels and $O(\log\Delta)$ bits of agent
memory it is possible to explore (with stop) all bounded-degree graphs of
maximum degree $\Delta$ in time $O(\Delta^{10}m)$.
Other approaches. If we assume that the port number via which the agent
entered to the current node is part of the input to the algorithm (such a
model is called a model with known inport) then tree exploration in linear
time can be achieved by a simple algorithm known in the literature as basic
walk [19]. This algorithm requires no memory (neither at the agent nor at the
nodes). However, if we require that the agent terminates at the starting
point, then $\Omega(\log n)$ bits are required if there is only memory at the
agent [10].

Random walk is a classical and well-studied process, where the agent in each
step moves to a neighbor chosen uniformly at random (or does not move with
some constant probability). Exploration using this method takes expected time
$\Omega(n\log n)$ [13] and $O(n^{3})$ [14], where for each of these bounds
there exists a graph class for which this bound is tight. Randomness alone
cannot ensure linear time of tree exploration, since expected time
$\Omega(n^{2})$ is required even for paths [24]. However approaches using
memory at the agent [21], local information on explored neighbors [5], or
local information on degrees [26] have shown that there are many methods to
speedup random walks.

Finally, to achieve fast tree exploration, usage of multiple parallel agents
is possible. A number of papers show that this approach allows to provide
faster exploration than using only a single agent in the deterministic model
with memory at the agent [8, 15, 27], with memory at the nodes [9, 20, 22] or
using randomness [8, 11, 12].

##  4 Upper bounds

###  4.1 Exploration in CleanMem model

In this section we show an algorithm exploring any tree in $O(n)$ steps using
$O(1)$ bits of memory at the agent and $O(\log d_{v})$ bits of memory at each
node $v$ of degree $d_{v}$ in CleanMem model.

The memory at each node is organized as follows. It contains two port pointers
(of $\lceil\log d_{v}\rceil$ bits each):

  * •

$v.\textsf{parent}$ – this pointer (at some point of the execution) contains
the port number leading to the root of the tree (i.e., the starting node of
the exploration),

  * •

$v.\textsf{last}$ – this pointer points to the last port taken by the agent
during the exploration

and two flags (of $1$ bit):

  * •

$v.\textsf{root}$ – this flag indicates whether the node is Root of the
exploration,

  * •

$v.\textsf{visited}$ – this flag indicates whether the node has already been
visited.

At each node, the initial state of last pointers is $1$, initial state of
parent is NULL and initial state of each flag is False.

The agent‘s memory contains one variable State that can take one of five
possible values: Initial, Exploring, ReturnFromParent, Completed, Terminated.

For simplicity of the pseudocode we use a flag $parentSet$. This flag does not
need to be remembered because it is set and accessed in the same round. It is
possible to write a more complicated pseudocode that does not require this
variable.

In our pseudocode, we use a procedure $\textsf{MOVE}{(}p)$, in which the agent
traverses an edge labelled with port $p$ from its current location. When the
agent changes its state to Terminated, it does not make any further moves.
Intuition of the algorithm. For the purpose of the analysis, assume that tree
$T$ is rooted at the initial position of the agent. The main challenge in
designing an exploration algorithm in this model is that the agent located at
some node $v$ may not know which port leads to the parent of $v$. Indeed, if
the agent knew which port leads to its parent, it could perform a DFS
traversal. The agent would traverse the edges corresponding to outgoing ports
in order $1,2,3,\dots,d_{v}$ (skipping the port leading to its parent) and
take the edge to its parent after completing the exploration of the subtrees
rooted at its current position. Note that it is possible to mark, which
outgoing ports have been already traversed by the agent using only a single
pointer at each node.

Since in our model, the agent does not know, which port leads to the parent,
we need a second pointer parent at each node. To set it correctly, we first
observe that in the model CleanMem, using flag visited, it is possible to mark
the nodes that have already been visited. Notice that when the agent traverses
some edge outgoing from $v$ in the tree for the first time and enters to a
node that has already been visited, then this node is certainly the parent of
$v$. We can utilize this observation to establish correctly parent pointer at
$v$ using state ReturnFromParent. When entering to a node in this state, we
know that the previously taken edge (port number of this edge is stored in
last) leads to the parent of $v$. Our algorithm also ensures, that after
entering a subtree, the agent leaves it once, and the next time it enters this
subtree, it is entirely explored. Finally, having correctly set pointers
parent at all the nodes, allows the agent to efficiently return to the
starting node after completing the exploration and flag root allows the agent
to terminate the algorithm at the starting node.

// Agent is at some node $v$ and the outgoing ports are
$\\{1,2,\dots,d_{v}\\}$

1 if  _$\textsf{State}=\textsf{Initial}$_ then

2 $v.\textsf{root}\leftarrow\texttt{True},$
$\textsf{State}\leftarrow\textsf{Exploring},$
$v.\textsf{visited}\leftarrow\texttt{True}$;

3 MOVE($v.\textsf{last}$) ;

4

5else

6

7 if  _$\textsf{State}=\textsf{ReturnFromParent}$_ then

$v.\textsf{parent}\leftarrow\textsf{last}$,
$\textsf{State}\leftarrow\textsf{Exploring}$;

// mark edge as leading to parent

8 $parentSet\leftarrow\texttt{True}$;

9 else $parentSet\leftarrow\texttt{False}$;

10 if  _(( $\textsf{State}=\textsf{Exploring}$ and $d_{v}=1$) or
$\textsf{State}=\textsf{Completed}$ or $parentSet=\texttt{True}$) and
$v.\textsf{root}=\texttt{False}$ and $v.\textsf{last}=d_{v}$ and
$v.\textsf{parent}\neq\textsf{NULL}$_ then

$\textsf{State}\leftarrow\textsf{Completed}$;

// exploration of this subtree completed

MOVE$(v.\textsf{parent})$ ;

// return to the parent

11

12 else if  _$\textsf{State}=\textsf{Completed}$ and
$v.\textsf{root}=\texttt{True}$ and $v.\textsf{last}=d_{v}$_ then

$\textsf{State}\leftarrow\textsf{Terminated}$;

// exploration of the whole tree completed

13

14 else

15 if  _$\textsf{State}=\textsf{Exploring}$ and
$v.\textsf{visited}=\texttt{True}$ and $parentSet=\texttt{False}$_ then

16 $\textsf{State}\leftarrow\textsf{ReturnFromParent}$;

17 else if  _$\textsf{State}=\textsf{Completed}$_ then

18 $\textsf{State}\leftarrow\textsf{Exploring}$, $v.\textsf{last}\leftarrow
v.\textsf{last}+1$;

19

20 else

21 if  _ $v.\textsf{visited}=\texttt{True}$_ then $v.\textsf{last}\leftarrow
v.\textsf{last}+1$;

22 else $v.\textsf{visited}\leftarrow\texttt{True}$;

23

24 MOVE$(v.\textsf{last})$ ;

25

26

Algorithm 1 Tree exploration in CleanMem model

######  Theorem 1.

Algorithm 1 explores any tree and terminates at the starting node in $O(n)$
steps in CleanMem model.

###### Proof.

First note that the algorithm marks the starting node with flag root (line 2).
The algorithm never returns to state Initial, hence only this node will be
marked with the root flag. The only line, where the agent terminates the
algorithm is line 1 hence the agent can only terminate in the starting node.
We need to show that the agent will terminate in every tree and before the
termination it will visit all the vertices and the time of the exploration
will be $O(n)$. Let us denote the starting node as Root and for any node $v$
different from Root, will call the single neighbor of $v$ that is closer to
Root as the parent of $v$.

We will show the following claim using induction over the structure of the
tree:

Claim 1: Assume that the agent enters to some previously unvisited subtree
rooted at $v$ with $n_{v}$ vertices for the first time in state Exploring in
step $t_{s}$. Then the agent:

  1. C.1

returns to the parent of $v$ for the first time in state Exploring (denote by
$t_{r}>t_{s}$ the step number of the first return from $v$ to its parent),

  2. C.2

goes back to $v$ in the state ReturnFromParent at step $t_{r}+1$,

  3. C.3

returns to the parent of $v$ for the second time in state Completed (denote by
$t_{f}>t_{r}+1$ the step number of the second return from $v$ to its parent),

  4. C.4

visits all the vertices of this subtree and spends $O(n_{v})$ steps within
time interval $[t_{s},t_{f}]$.

We will first show it for all the leaves. Then, assuming that the claim holds
for all the subtrees rooted at the children of some node $v$, we will show it
for $v$. To show this claim for any leaf $l$, consider the agent entering in
state Exploring to $l$. Upon the first visit to $l$, the agent sets the flag
$l.\textsf{visited}$ to True and leaves (without changing the state of the
agent) with port $1$. This proves C.1. In the next step, at the parent of $l$,
a state changes to ReturnFromParent and the agent uses the same port as during
the last time in parent of $l$. Therefore the agent moves back to $l$ (C.2)
and sets $l.\textsf{parent}\leftarrow 1$ (line 6). Then the agent changes its
state to Completed and moves to the parent (lines 1-1). This shows C.3. Node
$l$ was visited twice within the considered time steps, which shows C.4. This
completes the proof of the claim for all the leaves.

Now, consider any internal node $v$ of the tree (with $d_{v}>1$) and assume
that the claim holds for all its children. When the agent enters to $v$ for
the first time, it sets the flag $v.\textsf{visited}$ to True and moves to its
neighbor $w$ (while being in state Exploring) via port $1$.

Case 1: $w$ is the parent of $v$. This immediately shows C.1. If the parent of
$v$ is not Root, then it has the degree at least $2$, hence the agent will
evaluate the if-statement in line 1 to False. Thus the agent will execute line
1 and change its state to ReturnFromParent. The agent uses the same port as
during the previous visit of $w$, therefore the agent goes back to $v$ (C.2),
hence it will correctly set the pointer $v.\textsf{parent}$ (it will point to
the parent of $v$), which shows C.3.

Case 2: $w$ is a child of $v$. In this case we enter to a child of $v$. We
have by the inductive assumption (C.1), that the agent will return from $w$ to
$v$ in state Exploring. Since the agent enters to $v$ in state Exploring, then
the value of $parentSet$ is False and the agent executes line 1, transitions
to state ReturnFromParent and then line 1 it takes the same edge as during the
last visit to $v$, hence it moves back to node $w$ (C.2). By C.3 we get that
the next time the agent will traverses the edge from $w$ to $v$, it will be in
state Completed. Then the agent increments the $v.\textsf{last}$ pointer (line
1) and moves to the next neighbor of $v$ (line 1).

Thus the agent either finds the parent or explores the whole subtree rooted at
one of its children $w$ in $O(n_{w})$ steps (by the inductive assumption C.4).
An analogous analysis holds for ports $2,3,\dots,d_{v}$. When the agent
returns from the neighbor connected to $v$ via the last port $d_{v}$, it is
either in state Completed or ReturnFromParent (the second case happens if the
edge leading from $v$ to its parent has port number $d_{v}$). In both cases it
executes lines 1 and 1 and leaves to its parent (the pointer to parent is
established since the agent had traversed each outgoing edge, hence it moved
to its parent and correctly set the parent pointer).

By this way, the agent visits all the subtrees rooted at $v$‘s children
$w_{1},w_{2},\dots,w_{d_{v}-1}$ (or up to $w_{d_{v}}$ if $v=\textsf{Root}$).
Hence, the total number of steps for a node $v\neq\textsf{Root}$ is
$O\left(\sum\limits_{i=1}^{d_{v}-1}n_{w_{i}}\right)=O(n_{v})$ and
$v=\textsf{Root}$ it is
$O\left(\sum\limits_{i=1}^{d_{v}}n_{w_{i}}\right)=O(n)$.

To complete the proof of Theorem 1 we need to analyze the actions of the agent
at Root. Consider the actions of the agent at Root when the
$\textsf{Root}.\textsf{last}$ pointer takes values
$i=1,2,\dots,d_{\textsf{Root}}$. Let $v_{i}$ be the neighbor of Root pointed
by port number $i$ at Root. Observe that the agent at Root behaves similarly
as in all the other internal nodes (only exception is that the agent will
never enter Root in state ReturnFromParent, because by Claim $1$ the agent can
enter to it only in states Exploring or Completed, since the Root is a parent
of its every child). By Claim 1, the agent visits the whole subtrees rooted at
these nodes in time proportional to the number of nodes in these subtrees.
When the agent returns from node $v_{d_{\textsf{Root}}}$ in state Completed
then the agent terminates the algorithm in line 1. The total runtime is
proportional to the total number of nodes in the tree. ∎

###  4.2 Exploration in Token model

Intuition of the algorithm. The agent has a single token, which can be
$\textsf{DROP}{ped}$, $\textsf{TAKE}{n}$ and $\textsf{MOVE}{d}$ (i.e., carried
by the agent across an edge of the graph). Moreover, the agent has constant
memory which contains a State from set
$\\{\textsf{Initial},\textsf{Roam},\textsf{RR},\textsf{Down},\textsf{Up},\textsf{Terminated}\\}$.
Our algorithm ensures, that in states Roam and RR the agent does not hold the
token and in the remaining states, it holds the token. In these four states
the agent can eventually DROP it. Each node $v$ has degree denoted by $d_{v}$,
which is part of the input to the agent, when entering to a node. Moreover,
the memory at each node $v$ is organized into three variables:
$v.\textsf{last}$ and $v.\textsf{parent}$ of size $\lceil\log d_{v}\rceil$ and
a flag $v.\textsf{root}\in\\{\texttt{True},\texttt{False}\\}$ to mark the
starting node (the node with this flag set to True will be called Root). We
assume that in all vertices, variables last, parent and root have initially
any admissible value (if not, then the agent would easily notice it and change
such a value). Moreover, when the agent is entering to a node, it can see
whether the node contains the token or not.

We would like to perform a similar exploration as in CleanMem model – we will
use pointers last and parent as in Algorithm 1. However, the difficulty in
this model is that these pointers may have arbitrary initial values.
Especially, if the initial value of parent is incorrect, Algorithm 1 may fall
into an infinite loop. Hence in this section we propose a new algorithm that
handles dirty memory using a single token. In this algorithm the agent
maintains an invariant that the node with the token, and all the nodes on the
path from the token‘s location to the root are guaranteed to have correctly
set pointers to their parents. To explore new nodes, the agent performs a
Rotor-Router traversal, starting from node $v$ with the token to its neighbor
$w$ (by the invariant, the agent chooses $w$ as one of its children, not its
parent). During this traversal, the agent is resetting the parent pointers at
each node (and cleaning the root flag). The agent is using last as the pointer
for the purpose of Rotor-Router algorithm. The agent does not have to reset
last as the Rotor-Router requires no special initialization. Moreover, by the
properties of Rotor-Router the agent does not traverse the same edge twice in
the same direction before returning to the starting node. Since the agent
starts in the node with the token, it can notice that it completed a
traversal. During this traversal each edge is traversed at most twice (once in
each direction). Moreover, each node visited during this traversal has cleaned
memory (pointer parent points to NULL and root is set to False). After
returning to the node with the token, pointer $v.\textsf{last}$ points at $w$
and $w.\textsf{last}$ points at $v$. Hence it is possible to traverse this
edge (in a special state Down similar to ReturnFromParent from Algorithm 1)
and correctly set pointer $w.\textsf{parent}$ maintaining the invariant. After
moving the token down, the agent starts the Rotor-Router procedure again.
Since the agent is not cleaning the pointer last, the Rotor-Router will use
different edges than during the previous traversal. Thus, our algorithm
traverses every edge at most $6$ times. Preliminaries. For brevity, let us
introduce a variable Token associated with a vertex currently occupied by the
agent, which is $1$, when the agent meets the token and $0$ otherwise. If
$\textsf{Token}=1$, then the agent can TAKE. If the agent holds the token, it
can DROP it.

Additionally, we consider two substates of RR, depending on the value of Token
variable. Substate $\textsf{RR}_{0}$ is state RR, if variable
$\textsf{Token}=0$ at the node to which the agent entered in the considered
step. Similarly $\textsf{RR}_{1}$ indicates that the agent enters in state RR
to a node with $\textsf{Token}=1$. Note that this distinction is only for the
purpose of the analysis, and it does not influence the definition of the
algorithm. In our analysis, we will call
$\textsf{Initial},\textsf{Roam},\textsf{RR}_{0},\textsf{RR}_{1},\textsf{Down},\textsf{Up},\textsf{Terminated}$
_actions_ as these states (and substates) correspond to different lines
executed by the agent (see the pseudocode of Algorithm 2).

// Agent is at some node $v$ and the outgoing ports are
$\\{1,2,\dots,d_{v}\\}$

1 if  _$\textsf{State}=\textsf{Initial}$_ then

2 Clean(), $v.\textsf{last}\leftarrow 1$, DROP;

// mark the root for termination

3 $v.\textsf{root}\leftarrow\texttt{True}$;

4 $\textsf{State}\leftarrow\textsf{Roam}$;

5

6else if  _$\textsf{State}=\textsf{RR}$ and $\textsf{Token}=1$_ then

// substate $\textsf{RR}_{1}$

7 TAKE, $\textsf{State}\leftarrow\textsf{Down}$;

8

9else if  _$\textsf{State}=\textsf{RR}$ and $\textsf{Token}=0$_ then

// substate $\textsf{RR}_{0}$

10 Clean();

Progress() ;

// increment last

11

12else if  _$\textsf{State}=\textsf{Down}$_ then

13 DROP, $v.\textsf{parent}\leftarrow v.\textsf{last}$;

14 Progress();

15 $\textsf{State}\leftarrow\textsf{Roam}$;

IfUp() ;

// check if in a leaf

16

17else if  _$\textsf{State}=\textsf{Up}$_ then

18 DROP, Progress();

19 $\textsf{State}\leftarrow\textsf{Roam}$;

20 if  _$v.\textsf{last}=1$ and $v.\textsf{root}=\texttt{True}$_ then

21 $\textsf{State}\leftarrow\textsf{Terminated}$;

22 IfUp();

23

24else if  _$\textsf{State}=\textsf{Roam}$_ then

25 Clean(), $\textsf{State}\leftarrow\textsf{RR}$;

26

27if  _$\textsf{State}\neq\textsf{Terminated}$_ then

28 $\textsf{MOVE}{(v.\textsf{last})}$;

1 Procedure  _Clean()_

2 $v.\textsf{root}\leftarrow\texttt{False}$,
$v.\textsf{parent}\leftarrow\textsf{NULL}$;

1 Procedure  _Progress()_

2 $v.\textsf{last}\leftarrow(v.\textsf{last}\mod\;d_{v})+1$;

1 Procedure  _IfUp()_

2 if  _$v.\textsf{parent}=v.\textsf{last}$_ then

3 TAKE, $\textsf{State}\leftarrow\textsf{Up}$;

4

5

Algorithm 2 Tree exploration in Token model

We assume that Initial action is performed at time step $0$. Let Root denote
the initial position of the agent. Let $v.\textsf{last}(t)$ and
$v.\textsf{parent}(t)$ denote, respectively, the values of $v.\textsf{last}$
and $v.\textsf{parent}$ pointers at the end of the moment $t$. If $v$ is the
starting point of the $t$-th step, then we say that $v.\textsf{last}(t)$ is
the outport related to $t$-th moment. Moreover, $v.\textsf{last}(\cdot)$
cannot be changed until the node $v$ will be visited for the next time. Each
$\textsf{MOVE}{(\textsf{last})}$ involves traversing an edge outgoing from the
current position of the agent via port indicated by the current value of
variable last at the current position. Let $\textsf{Path}(v)$ denote a set of
all vertices, which are on the shortest path from Root to $v$, excluding Root.
Let $T_{v}$ denote the subtree of $T$ rooted at $v$, i.e., $(w\in
T_{v})\,\equiv\,(w=v\,\lor\,v\in\textsf{Path}(w))$. Let $T_{v,p}$ denote a
subtree of $T_{v}$, rooted at a node connected by edge labelled by outport $p$
at vertex $v$, i.e. if $p$ leads from $v$ to $w$ (where
$v\in\textsf{Path}(w)$), then $T_{v,p}=T_{w}$ (we do not define such the tree
when $p$ directs towards Root). We say that the action is performed away from
Root (downwards), if it starts in $v$ and ends in $T_{v}$. Otherwise the
action is towards Root (upwards). Let $\textsf{Tok}(t)$ and $\textsf{Ag}(t)$
be the positions of the token and the agent, respectively, at the end of the
moment $t$. Let $\textsf{Act}(t)$ denote the action performed during the
$t$-th step. Let the variable $v.\textsf{visited}(t)\in\\{0,1\\}$ indicates
whether $v$ was visited by Algorithm 2 until the moment $t$. Note that this
variable is not stored at the nodes and this notation is only for the
analysis.

Properties of the algorithm. Let us define the following set of properties
$\textsf{P}(t)$ (in this definition we denote $\textsf{Ag}(t)=w$) that
describe the structure of the walk and the interactions with the memory at the
nodes by an agent performing Algorithm 2.

  1. P.1

During $t$-th step

    1. (a)

Down and Roam actions are performed away from Root (downwards).

    2. (b)

Up and $\textsf{RR}_{1}$ actions are performed towards Root (upwards).

  2. P.2

$w\in T_{\textsf{Tok}(t)}$.

  3. P.3

If $w$ is visited for the first time at step $t$
($\textsf{Act}(t)\in\\{\textsf{Initial},\textsf{Roam},\textsf{RR}_{0}\\}$),
then it is also cleaned, which means that $w.\textsf{parent}$ is set to NULL
and $w.\textsf{root}$ is set to False.

  4. P.4

For every $v\in\textsf{Path}(\textsf{Tok}(t))$,
$v.\textsf{parent}(t)\neq\textsf{NULL}$.

  5. P.5

If $w.\textsf{visited}(t-1)=1$ and $w.\textsf{parent}(t-1)\neq\textsf{NULL}$,
then $\textsf{Act}(t)\not\in\\{\textsf{Roam},\textsf{RR}_{0}\\}$.

  6. P.6

If $w.\textsf{visited}(w,t)=1$ and $w.\textsf{parent}(t)\neq\textsf{NULL}$,
then $w.\textsf{parent}(t)$ directs towards Root.

  7. P.7

If the state at the end of $t$-th moment is Up, then $T_{w}$ is explored.

  8. P.8

If $t>0$, then for every $x\leqslant\textsf{Root}.\textsf{last}(t-1)$,
$T_{\textsf{Root},x}$ is explored before $t$-th moment.

  9. P.9

If $w.\textsf{parent}(t)=\textsf{NULL}$, then there do not exist
$s_{1}<s_{2}<t$ such that $w.\textsf{last}(s_{1})=w.\textsf{last}(t)\neq
w.\textsf{last}(s_{2})$, where $w.\textsf{parent}(s_{1})=\textsf{NULL}$
($w.\textsf{last}(\cdot)$ cannot be changed to the same value two times before
$w.\textsf{parent}(\cdot)$ was established).

  10. P.10

There do not exist $s_{1}<s_{2}<t$ such that
$w.\textsf{last}(s_{1})=w.\textsf{last}(t)\neq w.\textsf{last}(s_{2})$ and
$w.\textsf{parent}(s_{1})\neq\textsf{NULL}$ ($w.\textsf{last}(\cdot)$ cannot
be changed to the same value two times after $w.\textsf{parent}(\cdot)$ was
established).

######  Lemma 1.

Right before the $1-st$ moment, Initial phase of Algorithm 2 guarantees
$\textsf{P}(0)$.

###### Proof.

P.1$(0)$ does not depend on Initial. $\textsf{Root}.\textsf{last}(0)=1$
entails P.8$(0)$, because no other nodes were visited. P.2$(0)$, P.3$(0)$,
P.7$(0)$ and P.9$(0)$ are trivially true. Note that
$\textsf{Root}\not\in\textsf{Path}(\textsf{Tok}(0))$, since Root is excluded
from any such a path, hence P.4$(0)$. Moreover,
$\textsf{Root}.\textsf{parent}(0)=\textsf{NULL}$, so if-conditions of
P.10$(0)$, P.5$(0)$ and P.6$(0)$ are not fulfilled, so they are true. ∎

######  Lemma 2.

If Algorithm 2 satisfies $\textsf{P}(s)$ for all $s\leqslant t$, then it also
fulfills $\textsf{P}(t+1)$.

###### Proof.

In all the cases below we assume that the agent starts from node $v$ at the
end of $t$-th moment and during $(t+1)$-th step $\textsf{MOVE}{s}$ through
$v.\textsf{last}(t)$ to node $w$ and performs an action, depending on the
case.

CASE I. $\textsf{Act}(t+1)=\textsf{Roam}$
If $\textsf{Act}(t+1)=\textsf{Roam}$, then
$\textsf{Act}(t)\in\\{\textsf{Down},\textsf{Up},\textsf{Initial}\\}$ and
consequently $\textsf{Act}(t)$ $\textsf{DROP}{s}$ the token at $v$. If
$v=\textsf{Root}$, then P.1$(t+1)$ is true because the MOVE during $(t+1)$-st
time step is clearly away from the root. Otherwise, from P.4$(t)$, we get
$v.\textsf{parent}(t)\neq\textsf{NULL}$ and
$\textsf{Act}(t)\neq\textsf{Initial}$. Thence
$\textsf{Act}(t)\in\\{\textsf{Down},\textsf{Up}\\}$ thus it end with IfUp()
procedure, which would give $\textsf{Act}(t+1)=\textsf{Up}$, if we had
$v.\textsf{last}(t)=v.\textsf{parent}(t)$, but since
$\textsf{Act}(t+1)=\textsf{Roam}$ we get
$v.\textsf{last}(t)=v.\textsf{parent}(t)$. Since due to P.6$(t)$, parent at
$v$ is set correctly, hence $w\not\in\textsf{Path}(v)$ and the MOVE during
$(t+1)$-st time step is away from the root which gives us P.1$(t+1)$. Moreover
$\textsf{Tok}(t)=v$, so also P.2$(t+1)$ is clearly true. Notice that Roam
always cleans $w$, and it neither moves the token nor changes
$v.\textsf{last}(\cdot)$, so P.3$(t+1)$, P.4$(t+1)$, P.9$(t+1)$ and
P.10$(t+1)$ are also true. We already know that the MOVE during $(t+1)$-st
time step was away from the Root thus P.8$(t+1)$ holds.
Assume, that $v\neq\textsf{Root}$. If $w.\textsf{visited}(t)=1$ and
$w.\textsf{parent}(t)\neq\textsf{NULL}$, then there exists $s\leqslant t$ such
that $w$ was visited by $\textsf{Act}(s)=\textsf{Down}$ action which is the
only action which establishes parent pointer at $w$ (recall that upon the
first visit at $w$ the pointer was cleaned), hence $\textsf{Tok}(s)=w$. By
P.4$(s)$ and P.1$(t+1)$, we get $v.\textsf{parent}(s)\neq\textsf{NULL}$.
Moreover, by P.6$(t)$ and P.5$(t)$, the parent‘s pointer cannot be changed
during $\textsf{Act}(t+1)$. From P.1$(s)$ and P.1$(t)$, we have
$v.\textsf{last}(s)=v.\textsf{last}(t)$, so by P.10$(t)$,
$v.\textsf{last}(\cdot)$ was not changed between the moments $s$ and $t$.
However $v=\textsf{Tok}(t)$, so by P.1$(s^{\prime})$, for $s^{\prime}\leqslant
t$, there exists a moment $u$, such that $s<u<t$, $\textsf{Ag}(u-1)=w$ and
$\textsf{Act}(u)=\textsf{Up}$ (the only action which moves the token upwards).
Notice that $\textsf{Act}(u)=\textsf{Up}$ invokes Progress() method, which
increases the port‘s pointer by $(1\mod\;d_{v})$, so $v.\textsf{last}(\cdot)$
did not change between the moments $s$ and $t$ and $v$ has to be a leaf of the
tree. However, from P.1$(t+1)$, $w$ is a child of $v$, so it is not a leaf. To
complete the contradiction, showing P.5$(t+1)$, let us consider the opposite
case, when $v=\textsf{Root}$. Then, the proof is very similar. The only
difference is that we need to use P.9$(t)$ instead of P.10$(t)$, because
$\textsf{Root}.\textsf{parent}(\cdot)\equiv\textsf{NULL}$, as
$\textsf{Root}.\textsf{parent}(\cdot)$ can be established only by Down action,
which cannot be performed towards Root from P.1$(s^{\prime})$, for
$s^{\prime}\leqslant t$).
From P.5$(t+1)$ we know that $w.\textsf{parent}(t)=\textsf{NULL}$, so we
simply get P.6$(t+1)$. P.7$(t+1)$ is independent of Roam action.

CASE II. $\textsf{Act}(t+1)=\textsf{RR}_{0}$
Properties P.1$(t+1)$ and P.7$(t+1)$ are independent of $\textsf{RR}_{0}$
action. Realize that $\textsf{RR}_{0}$ action cannot be taken from $v$ to
Root, because of P.2$(t)$, so $\textsf{Ag}(t+1)\neq\textsf{Root}$ and
P.8$(t+1)$ is true. If $\textsf{Act}(t+1)=\textsf{RR}_{0}$, then
$\textsf{Act}(t)\in\\{\textsf{RR}_{0},\textsf{Roam}\\}$. Hence
$v\neq\textsf{Tok}(t)$ and P.2$(t+1)$ remains fulfilled.
$\textsf{Tok}(t+1)=\textsf{Tok}(t)$, so
$w\not\in\textsf{Path}(\textsf{Tok}(t+1))$ and consequently P.4$(t+1)$ remains
true. $\textsf{RR}_{0}$ cleans $w$, so P.3$(t+1)$ and P.6$(t+1)$ are obvious.
Note that $\textsf{parent}(w,t+1)=\textsf{NULL}$, so by P.5$(s^{\prime})$, for
$s^{\prime}\leqslant t$, it was always NULL since the first visit of $w$. This
immediately shows P.10$(t+1)$ and P.5$(t+1)$.
Assume that $s_{1}$ is the first moment, when
$w.\textsf{last}(s_{1})=w.\textsf{last}(t+1)$ and $w.\textsf{last}(\cdot)$ was
changed meanwhile. Since $w.\textsf{last}(\cdot)$ can be incremented only by
$(1\mod\;d_{w})$, there exists a moment $s_{2}$ such that $s_{1}<s_{2}<t+1$
and $w.\textsf{last}(s_{2})$ directs upwards to some vertex $v_{p}$, but
$w.\textsf{last}(s_{2}-1)$ is not. Moreover, assume that $w$ was visited for
the first time at moment $s_{0}\leqslant s_{1}$. This means that
$\textsf{Ag}(s_{0}-1)=v_{p}$. By P.3$(s_{0})$,
$\textsf{Act}(s_{0})\in\\{\textsf{Roam},\textsf{RR}_{0}\\}$. If
$\textsf{Act}(s_{0})=\textsf{Roam}$, then $v_{p}=\textsf{Tok}(s_{2})$,
$\textsf{Act}(s_{2}+1)=\textsf{RR}_{1}$ and
$\textsf{Act}(s_{2}+2)=\textsf{Down}$, so
$w.\textsf{parent}(s_{2}+2)\neq\textsf{NULL}$, where $s_{2}+2\leqslant t+1$.
If $\textsf{Act}(s_{0})=\textsf{RR}_{0}$, then there exists the first moment
$s_{3}$, where $s_{2}<s_{3}\leqslant t+1$, such that $\textsf{Act}(s_{3})$
starts in $v_{p}$ and ends in $w$. Since $\textsf{Act}(s_{0})=\textsf{RR}_{0}$
is preceded either by Roam or another $\textsf{RR}_{0}$ action, therefore
$v_{p}.\textsf{parent}(s_{0})=\textsf{NULL}$. Moreover, we know that
$v_{p}.\textsf{last}(s_{0}-1)$ directs to $w$, so
$v_{p}.\textsf{last}(s_{0}-1)=v_{p}.\textsf{last}(s_{3})$. Note that from
P.2$(s^{\prime})$ for $s_{0}\leqslant s^{\prime}\leqslant s_{2}$, we obtain
that the agent does not meet the token between the moments $s_{0}$ and
$s_{2}$, so $\textsf{Act}(s^{\prime})=\textsf{RR}_{0}$ for $s_{0}\leqslant
s^{\prime}\leqslant s_{2}+1$. Therefore $v_{p}.\textsf{last}(\cdot)$ is
incremented by $(1\mod\;d_{v_{p}})$ at the moment $s_{2}+1$. Since $w$ is
further from Root than $v_{p}$, $d_{v_{p}}>1$, and in consequence, as we know
that $v_{p}.\textsf{last}(s_{0}-1)=v_{p}.\textsf{last}(s_{3})$, then from
P.9$(s^{\prime})$, for $s^{\prime}\leqslant t$, we conclude that
$v_{p}.\textsf{parent}(s_{3})\neq\textsf{NULL}$. Hence the $s_{3}$-th step is
the Roam action and $w.\textsf{last}(s_{3})$ direct upwards. Therefore
$\textsf{Act}(s_{3}+1)=\textsf{RR}_{1}$ and
$\textsf{Act}(s_{3}+2)=\textsf{Down}$, and in consequence,
$w.\textsf{parent}(s_{3}+2)\neq\textsf{NULL}$. This completes the proof of
P.9$(t+1)$.

CASE III. $\textsf{Act}(t+1)=\textsf{RR}_{1}$
Realize that $w=\textsf{Tok}(t)$, so $w.\textsf{visited}(t)=1$ and P.3$(t+1)$
follows from P.3$(t)$. Moreover, from P.2$(t)$, the agent has to move upwards
during $\textsf{Act}(t+1)$, so P.1$(t+1)$, what entails also P.2$(t+1)$.
$\textsf{RR}_{1}$ does not change any port or parent and does not move the
token, so it is independent of P.8$(t+1)$, P.4$(t+1)$, P.5$(t+1)$, P.7$(t+1)$
and P.6$(t+1)$. Moreover then P.10$(t+1)$ and P.9$(t+1)$ follows from
P.10$(t)$ and P.9$(t)$ respectively.

CASE IV. $\textsf{Act}(t+1)=\textsf{Down}$
Realize that $\textsf{Act}(t)=\textsf{RR}_{1}$ was performed upwards (due to
P.1$(t)$) and $v.\textsf{last}(t-1)$ was not changed since the last visit.
Therefore $w=\textsf{Ag}(t+1)=\textsf{Ag}(t-1)$ and hence $(t+1)$-st step is
performed downwards, what shows P.1$(t+1)$. Moreover, it entails that
$\textsf{Root}.\textsf{last}(t)=\textsf{Root}.\textsf{last}(t+1)$, so Down
action is independent of P.8$(t+1)$. Down action $\textsf{DROP}{s}$ the token,
so P.2$(t+1)$ holds. Since $\textsf{Ag}(t+1)=\textsf{Ag}(t-1)$, P.3$(t+1)$
follows from P.3$(t)$. Down action $\textsf{MOVE}{s}$ the token downwards
(from P.1$(t+1)$), but establishes $w.\textsf{parent}(t+1)\neq\textsf{NULL}$,
so P.4$(t)$ gives P.4$(t+1)$. Since $\textsf{Ag}(t+1)=\textsf{Ag}(t-1)$,
$\textsf{Act}(t)=\textsf{RR}_{1}$ and
$\textsf{Act}(t-1)\in\\{\textsf{Roam},\textsf{RR}_{0}\\}$, so
$w.\textsf{parent}(t-1)=w.\textsf{parent}(t)=\textsf{NULL}$. Therefore
P.10$(t+1)$ is fulfilled. This also shows that P.9$(t+1)$ and P.5$(t+1)$ are
independent of Down action. Down action establishes
$w.\textsf{parent}(t+1)=w.\textsf{last}(t-1)$, but
$\textsf{Act}(t)=\textsf{RR}_{1}$, so from P.1$(t)$, $w.\textsf{parent}(t+1)$
directs towards Root. If the agent during this step changes its state to Up,
then $w.\textsf{parent}(t+1)=(w.\textsf{parent}(t+1)\mod\;d_{w})+1$, so $w$ is
a leaf, so whole $T_{w}$ is explored and P.7$(t+1)$ is fulfilled.

CASE V. $\textsf{Act}(t+1)=\textsf{Up}$
Realize that Up state can be obtained only during the execution of IfUp()
method, only when $v.\textsf{parent}(t)=v.\textsf{last}(t)$. From
P.3$(s^{\prime})$, for $s^{\prime}\leqslant t$, every parent‘s pointer of
vertices visited until the $t$-th moment was cleaned, so P.6$(t)$ shows that
$v.\textsf{last}(t)$ directs upwards, which proves P.1$(t+1)$.
If $w\neq\textsf{Root}$, then P.8$(t+1)$ does not depend on Up move.
Otherwise, let $w=\textsf{Root}$, then $\textsf{Root}.\textsf{last}(\cdot)$ is
increased at the moment $t+1$, so P.8$(t+1)$ follows from P.8$(t)$ if
$\textsf{Root}.\textsf{last}(t)\neq d_{\textsf{Root}}$. Otherwise,
$\textsf{Root}.\textsf{last}(t+1)=1=\textsf{root}$, so Algorithm 2 is
Terminated.
Since Up is performed towards Root during the $(t+1)$-st step,
$\textsf{Tok}(t)=\textsf{Ag}(t)\neq\textsf{Root}$ had to be in
$T_{\textsf{Root},\textsf{last}(\textsf{Root},t)}$. If $\textsf{Act}(t+1)$
ends in Root, then P.7(t) shows that
$T_{\textsf{Root},\textsf{Root}.\textsf{last}(t)}$ is explored, and from
P.8$(t)$, we get P.8$(t+1)$.
As Up action $\textsf{DROP}{s}$ the token, P.2$(t+1)$ is obviously true, what
also implies P.9$(t+1)$. $\textsf{Act}(t+1)$ is performed upwards (by
P.1$(t+1)$), so $w.\textsf{visited}(t)=1$ and P.3$(t+1)$ follows from
P.3$(s^{\prime})$, for $s^{\prime}\leqslant t$. Up action does not change
parent‘s pointer, so it is independent of P.4$(t+1)$, P.6$(t+1)$ and also
P.5$(t+1)$.
Assume that $s$ is the first moment when
$w.\textsf{parent}(s)\neq\textsf{NULL}$. Therefore
$\textsf{Act}(s)=\textsf{Down}$, so
$w.\textsf{last}(s)=(w.\textsf{parent}(s)\mod\;d(w))+1$. Since the
$w.\textsf{last}(\cdot)$ can be only incremented by $1$ modulo $d(w)$, then
the first repetition of the port‘s pointer may be only
$w.\textsf{last}(t+1)=w.\textsf{last}(s)$ after
$\textsf{Act}(t+1)=\textsf{Up}$. Assume that the node $w$ was visited last
time at some step $s_{2}$. Then
$w.\textsf{last}(s_{2})=w.\textsf{parent}(s_{2})$, which cannot change,
according to P.6$(s^{\prime})$, for $s_{2}\leqslant s^{\prime}\leqslant t+1$,
so in order to get back to $w$, $\textsf{Act}(t+1)$ has to be preformed
downwards, contrary to P.1$(t+1)$. This proves P.10$(t+1)$.
If $\textsf{Act}(t+1)=\textsf{Up}$ ends up in the state Up, then
$w.\textsf{parent}(t)=(w.\textsf{last}(t)\mod\;d(w))+1$ and
$T_{v}=T_{w,w.\textsf{last}(t)}$ is explored by P.7$(t)$. Moreover, since
$w.\textsf{parent}(t)\neq\textsf{NULL}$, there exists the moment $s$, such
that $v$ was visited during $\textsf{Act}(s)=\textsf{Down}$, when
$w.\textsf{parent}(\cdot)$ was established, so by P.10$(s)$ for $s\leqslant
s^{\prime}\leqslant t+1$, every outport of $w$ was used once (because
$w.\textsf{last}(s)=(w.\textsf{parent}(s)\mod\;d_{w})+1$), so $w$ was visited
only upwards in steps from $s+1$ to $t$. From P.1$(s^{\prime})$ and
P.6$(s^{\prime})$ for $s\leqslant s^{\prime}\leqslant t+1$,
$w.\textsf{last}(\cdot)$ was changed only during Up actions, what implies that
every $T_{w,w.\textsf{last}(s^{\prime})}$ was explored by P.7$(s^{\prime})$
for $s\leqslant s^{\prime}\leqslant t+1$, so $T_{v}$ was explored as well,
what shows P.7$(t+1)$. ∎

We will use properties $\textsf{P}(t)$ to show correctness and time complexity
of our Algorithm 2.

Initial ptClean()$\textsf{last}=1$$\textsf{root}=\texttt{True}$DROP Roam
Clean() $\textsf{RR}_{1}$ TAKE $\textsf{RR}_{0}$ ptClean()Progress() Down
ptDROPProgress() Up ptDROPProgress() Terminated End$\textsf{Tok}=1$with
Tok$\textsf{parent}=\textsf{last}$TAKE then
MOVEpt$\textsf{parent}=\textsf{last}$TAKE then
MOVE$\textsf{parent}\neq\textsf{last}$$\textsf{Tok}=0$$\textsf{Tok}=0$$\textsf{Tok}=1$$\textsf{parent}\neq\textsf{last}$pt$\textsf{last}=1$$\textsf{root}=\texttt{True}$
Figure 1: Illustration of actions and state transitions in Algorithm 2.

######  Theorem 2.

Algorithm 2 explores any tree and terminates at the starting node in at most
$6(n-1)$ steps in Token model.

###### Proof.

Using the induction from lemmas 1 and 2, we get that Algorithm 2 satisfies
$\textsf{P}(t)$ for each step $t$. First of all, from P.3, all visited
vertices are cleaned upon the first visits.
Consider some vertex $v$ and its arbitrary outport $p$. If
$v\neq\textsf{Root}$, then from P.9 and P.10, $p$ may be used two times
instantly after the incrementation of $v.\textsf{last}(\cdot)$ (once when
$v.\textsf{parent}(\cdot)=\textsf{NULL}$ and once when
$v.\textsf{parent}(\cdot)\neq\textsf{NULL}$). Realize that, when
$v=\textsf{Root}$, then from P.2 and the fact, that any vertex with the token
cannot be cleaned by $\textsf{RR}_{0}$ and Roam moves, we claim that
$\textsf{Root}.\textsf{parent}(\cdot)$ will always be NULL. By P.9, $p$ may be
used once instantly after the incrementation of
$\textsf{Root}.\textsf{last}(\cdot)$. Moreover, regardless of the choice of
$p$, it may be used also after Roam or $\textsf{RR}_{1}$ action without a
change of $v.\textsf{last}(\cdot)$.
Case 1. Assume that $\textsf{Act}(t)=\textsf{RR}_{1}$ is taken via port $p$.
From P.1$(t)$ and P.2$(t)$, $p$ directs upwards towards the token. Then
$\textsf{Act}(t+1)=\textsf{Down}$ is performed downwards (from P.1$(t+1)$) via
the same edge as $p$ (but with the opposite direction) and changes the
position of the token to $\textsf{Tok}(t+1)=v$ and establishes
$v.\textsf{parent}(t+1)\leftarrow p$. By P.1, $p$ cannot be used during Roam
action. Realize that if $p=v.\textsf{last}(s-1)$ for some moment $s>t$ and
$\textsf{Act}(s)=\textsf{RR}_{1}$, then $\textsf{Tok}(s-1)$ is one step
towards Root from $v$ (from P.1$(s)$). Since the token can be moved only
during Up and Down actions, then there exists a moment $s^{\prime}$ such that
$t<s^{\prime}<s$ and $\textsf{Act}(s^{\prime})=\textsf{Up}$ changes the
position of the token from $v$ to $\textsf{Tok}(s)$. However then
$\textsf{Tok}(s).\textsf{last}(s)\neq\textsf{Tok}(s).\textsf{last}(s-1)$
($\textsf{Tok}(s)$ is not a leaf) and by P.10, P.6 and P.4, it cannot be
changed back since $\textsf{parent}(\textsf{Tok}(s))\neq\textsf{NULL}$.
Case 2. Assume that $\textsf{Act}(t)=\textsf{Roam}$ is taken from node
$v=\textsf{Tok}(t-1)$ via port $p$ (downwards, by P.1$(t)$). The first action
after time $t$, which leads to the token, is always $\textsf{RR}_{1}$.
However, as showed before, after $\textsf{RR}_{1}$ action there is an instant
Down action, which moves the token via $p$ to some vertex $w$ and sets
$w.\textsf{parent}\neq\textsf{NULL}$. Hence by P.5, Roam action cannot be
performed via $p$ once again. By P.1, $p$ cannot be used during
$\textsf{RR}_{1}$ action.

Our considerations show that each outport can be used at most $3$ times. Since
each tree of size $n$ has $2(n-1)$ outports, Algorithm 2 terminates after at
most $6(n-1)$ moves.

It remains to show that all vertices are then explored. Realize that Algorithm
2 terminates in $t+1$-st moment only when the agent is in $\textsf{Tok}(t)$,
$\textsf{Tok}(t).\textsf{last}(t)=1$,
$\textsf{Tok}(t).\textsf{root}=\texttt{True}$ and the state is Up at the end
of $t$-th moment. From P.3, we know that the first visit in some $v$ sets the
root flag to True in Root and to False in all other nodes, and this flag does
not change (Roam and $\textsf{RR}_{0}$ do not clean the vertices with the
token, so by P.2, Root cannot be cleaned by these moves). Hence the
termination entails $\textsf{Tok}(t)=\textsf{Root}$. Since
$\textsf{Root}.\textsf{parent}(t)$ $=\textsf{NULL}$, then from P.9 we know
that each port $p$ in Root will be set by $\textsf{Root}.\textsf{last}(\cdot)$
only once (since the first moment) and P.8 means that each subtree
$T_{\textsf{Root},p}$ for $p\in\\{1,\ldots,d_{\textsf{Root}}\\}$ were explored
before returning to Root, hence the exploration $T_{\textsf{Root}}$ was
completed. ∎

##  5 Path with dirty memory

In this section we analyze exploration of paths with one bit of memory at each
node and one bit at the agent. We show that in this setting, in the DirtyMem
model, the exploration of the path sometimes requires $\Omega(n^{2})$ steps.

Notation. In the following lower bound on the line, we will focus on the
actions of the algorithm performed in vertices with degree $2$. In such
vertices, there are four possible inputs to the algorithm
$S=\\{(0,0),(0,1),(1,0),(1,1)\\}$, where in a pair $(a,v)$, $a$ denotes a bit
on the agent and $v$ is a bit saved on the vertex. Let us denote the sets of
agent and vertex states by $\mathrm{As}$ and $\mathrm{Vs}$ respectively. We
also use elements from $\mathrm{Ps}=\\{0,1\\}$ to denote ports in vertices of
degree $2$. Morevoer, a shorthand notation ′ indicates the inverted value of a
bit. For example, if $a=0$, then $a^{\prime}=1$ and vice versa. The goal of
this section is to prove:

######  Theorem 3.

Any algorithm that can explore any path in the DirtyMem model with one bit at
the agent and one bit at each node requires time $\Omega(n^{2})$ to explore
some worst-case path with $n$ nodes.

Assume, for a contradiction, that there exists algorithm $\mathcal{A}$, which
explores any path in $o(n^{2})$ steps. Without a loss of generality, we may
assume that the adversary always sets the agent in the middle point of the
path. For algorithm $\mathcal{A}$, for any $s\in S$, by $A(s),V(s),P(s)$ we
denote respectively, the returned agent state, vertex state and the chosen
outport in each vertex with degree $2$. Moreover, we denote
$R_{3}(s):=(A(s),V(s),P(s))$ and $R_{2}(s):=(A(s),V(s))$. We will show that
$\mathcal{A}$ either falls into an infinite loop or performs no faster than
Rotor-Router.

A proof of Theorem 3 is divided naturally in several parts. In the first one,
we provide several properties of potential algorithms $\mathcal{A}$ that can
eventually explore the path in $o(n^{2})$ time. These properties are utilized,
among others, in the second part, where we prove that the agent does not
change its internal state every time (Lemma 5), however it has to change the
state of the vertex in each step (Lemma 6). Further, we check two algorithms
(called X and Y), which surprisingly turn out to explore the path even slower
than the Rotor-Router algorithm (Lemma 7). The analysis of those two
algorithms turns out to be quite challenging. Next we show that if three
states of $\mathcal{A}$ return the same outport, then either it falls into an
infinite loop or explores the path in $\Omega(n^{2})$ steps. In the latter
part we consider the rest of amenable algorithms, which can either be reduced
to previous counterexamples or fall into an infinite loop.

######  Fact 1.

$(\forall\;a\in\mathrm{As})(\exists\;v\in\mathrm{Vs})\;A(a,v)=a^{\prime}$.

###### Proof.

Assume that $(\exists\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;A(a,v)=a$.
If $a$ is the initial state of the agent, then the agent will never change its
state before reaching an endpoint of the path. Hence, the time to reach the
endpoint cannot be faster than Rotor-Router algorithm, hence the adversary can
initialize ports in such a way that the endpoint will be reached after
$\Omega(n^{2})$ steps. If $a^{\prime}$ is the starting state, then either the
agent state never changes which reduces to the previous case or
$A(a^{\prime},w)=a$ for some $w\in\mathrm{Vs}$. Then, adversary sets $w$ as
the initial state of the starting vertex and after the first step the state of
the agent changes to $a$ and by the same argument as in the first case, the
algorithm requires $\Omega(n^{2})$ steps. ∎

######  Fact 2.

$(\forall\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;R_{2}(a,v)\neq(a,v)$.

###### Proof.

We will show that otherwise algorithm $\mathcal{A}$ falls into an infinite
loop for some initial state of the path. Assume that $R_{3}(a,v)=(a,v,p)$ for
some $a\in\mathrm{As},\ v\in\mathrm{Vs},\ p\in\mathrm{Ps}$. Then if $a$ is the
starting agent state, the agent falls into an infinite loop on the left gadget
from Fig. 2 (double circle denotes the starting position of the agent and $a$
above the node indicates its initial state). If $a^{\prime}$ is the starting
state, then by Fact 1, $(\exists\;w\in\mathrm{Vs})\;A(a^{\prime},w)=a$. Let
$q=P(a^{\prime},w)$ and note that the agent falls into an infinite loop in the
right gadget from Fig. 2. ∎

$v$ $a$ $v$ $p$$p^{\prime}$$p$$p^{\prime}$

$w$ $a^{\prime}$ $v$ $v$ $q$$p$$p^{\prime}$$p$$p^{\prime}$$q^{\prime}$

Figure 2: Two looping gadgets for an algorithm with $R_{2}(a,v)=(a,v)$.

In the following series of facts we will prove some properties that
$\mathcal{A}$ has to satisfy.

######  Lemma 3.

Fix any $a\in\mathrm{As}$ and $v\in\mathrm{Vs}$. Algorithm $\mathcal{A}$ does
not satisfy the following condition:

$R_{2}(a,v)=(a^{\prime},v)\land A(a^{\prime},v)=A(a^{\prime},v^{\prime})~{}.$

###### Proof.

Assume that the formula holds for some $a\in\mathrm{As}$ and $v\in\mathrm{Vs}$
and we will show that in such a case $\mathcal{A}$ would fall into an infinite
loop for some initializations of the path. From Fact 1, we obtain, that
$A(a^{\prime},v)=A(a^{\prime},v^{\prime})=a$. Denote $P(a,v)=p$ and
$V(a^{\prime},v)=y$.

If $y=v$, then let $P(a^{\prime},v)=p^{\prime}$, and the following initial
state of the path results in an infinite loop:

$v$ $a$ $v$ $p$$p$$p^{\prime}$$p^{\prime}$

In the opposite case, where $y=v^{\prime}$, the agent would fall into an
infinite loop on the following gadget:

$v$ $a$ $v^{\prime}$ $v$ $p$$p^{\prime}$$p^{\prime}$$p$$p$$p^{\prime}$

Indeed, $R_{3}(a,v)=(a^{\prime},v,p)$, hence in the first step, the agent
moves to the middle vertex, changes its state to $a^{\prime}$, and keeps $v$
as the state of the first vertex. At the middle vertex when the agent state is
$a^{\prime}$, then it always changes its state to $a$ and moves to one of the
outer vertices (independent on the vertex state of the middle node). But since
the outer vertices are both in state $v$, the agent returns to the middle
vertex, and so on, which is an infinite loop. ∎

The following fact characterises features of an algorithm, in which some state
$a$ of the agent is flipped for both states of a vertex.

######  Fact 3.

Fix any $a\in\mathrm{As}$. If $(\forall\;v\in\mathrm{Vs})\;A(a,v)=a^{\prime}$,
then:

  1. i.

$(\forall\;w\in\mathrm{Vs})\;R_{2}(a^{\prime},w)\neq(a,w)$,

  2. ii.

$(\forall\;w\in\mathrm{Vs})\;V(a^{\prime},w)=w^{\prime}$,

  3. iii.

$(\exists\;w\in\mathrm{Vs})\;R_{2}(a^{\prime},w)=(a,w^{\prime})$.

###### Proof.

For each $w\in\mathrm{Vs}$, Claim i. follows from Lemma 3 for $a^{\prime},w$.
Claim ii. follows from Fact 2 and Claim i.. Claim iii. follows from Fact 1 and
Claims i., ii.. ∎

######  Fact 4.

For any $v\in\mathrm{Vs}$, $R_{2}(a,v)\neq(a^{\prime},v)$ or
$R_{2}(a^{\prime},v)\neq(a,v)$.

###### Proof.

Let $P(a,v)=p$ and $P(a^{\prime}v)=q$. Observe that if
$(\exists\;v\in\mathrm{Vs})\;R_{3}(a,v)=(a^{\prime},v,p)\ \land\
R_{3}(a^{\prime},v)=(a,v,q)$, then the agent would fall into an infinite loop
on the following gadget:

$v$ $v$ $p$$q^{\prime}$$q$$p^{\prime}$

Indeed, if the agent‘s starting state is $a$ (respectively $a^{\prime}$), the
adversary chooses its starting position as the right (respectively left)
vertex and the agent never exits from the gadget. ∎

######  Lemma 4.

Let $a\in\mathrm{As}$. If $(\forall\;v\in\mathrm{Vs})\;P(a,v)=p$, then
$(\exists\;w\in\mathrm{Vs})\;A(a^{\prime},w)=a^{\prime}\land
P(a^{\prime},w)=p^{\prime}~{}.$

###### Proof.

First observe that $(\exists\;w\in\mathrm{Vs})P(a^{\prime},w)=p^{\prime}$,
since otherwise the algorithm always takes the same port $p$ in every node
with degree $2$ and thence can be trivially looped.

Observe that, if
$(\forall\;w\in\mathrm{Vs})\;P(a^{\prime},w)=p^{\prime}\Rightarrow
A(a^{\prime},w)=a$, then the agent always changes its state to $a$ whenever we
takes port $p^{\prime}$ and from the assumption, it always takes port $p$ in
state $a$. Consider the following gadget (where $\ast$ denotes any vertex
state, possibly different at each vertex):

$*$ $\ast$ $\ast$ $\ast$
$p^{\prime}$$p$$p$$p^{\prime}$$p^{\prime}$$p^{\prime}$$p$$p$$p^{\prime}$$p^{\prime}$

After entering to any of the outer vertices, the agent is certainly in state
$a$, because it can only enter it via port $p^{\prime}$. Hence in the next
step it takes port $p$. Thus it cannot exit from such a gadget. We obtain a
contradiction, so the implication cannot be true, what completes the proof of
the lemma. ∎

The following fact is a direct conclusion of Lemma 4:

######  Fact 5.

Let $a\in\mathrm{As}$. If $(\forall\;v\in\mathrm{Vs})\;A(a^{\prime},v)=a$,
then $P(a,v)\neq P(a,v^{\prime})$.

The next lemma shows that the agent does not change its internal state in
every step.

######  Lemma 5.

Fix any $a\in\mathrm{As}$. If $(\forall\;v\in\mathrm{Vs})\;A(a,v)=a^{\prime}$,
then $(\exists\;w\in\mathrm{Vs})\;R_{2}(a^{\prime},w)=(a,w^{\prime})\ \land\
R_{2}(a^{\prime},w^{\prime})=(a^{\prime},w)$.

###### Proof.

By Fact 3 we know that

$(\exists\;w\in\mathrm{Vs})\;R_{2}(a^{\prime},w)=(a,w^{\prime})\ \land\
\left(R_{2}(a^{\prime},w^{\prime})=(a^{\prime},w)\ \lor\
R_{2}(a^{\prime},w^{\prime})=(a,w)\right)~{}.$

In order to prove 5, let us assume that $R_{2}(a^{\prime},w^{\prime})=(a,w)$,
what implies that the agent changes its internal state in each step (i.e.
$(\forall\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;A(a,v)=a^{\prime}$). A
symmetric application of Fact 3 shows that
$(\exists\;v\in\mathrm{Vs})\;R_{2}(a,v)=(a^{\prime},v^{\prime})\ \land\
R_{2}(a,v^{\prime})=(a^{\prime},v)$ (because $A(a,v^{\prime})=a^{\prime}$).
Hence we obtained that
$(\forall\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;R_{2}(a,v)=(a^{\prime},v^{\prime})$,
what means that the states of vertices are changed upon each visit of the
agent as well.

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$

We want to show that for such an algorithm:

$(\forall\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;P(a,v)\neq
P(a,v^{\prime}).$ (1)

Assume for contradition that for some $a\in\mathrm{As},\ v\in\mathrm{Vs},\
p\in\mathrm{Ps}$ we have $P(a,v)=P(a,v^{\prime})=p$. Observe that, in this
case, in every step at a node with degree $2$ the agent changes its state, so
at least one of every two consecutive steps at nodes with degree $2$ is via
port $p$. This shows, that on a path, where port $p$ always points towards the
starting position of the agent, the agent cannot reach more than $2$ steps
away from its starting position, hence it cannot explore the whole path.
Thence Equation 1 is proved for such the algorithm.

Now, let us consider the following two cases:

Case A: $P(a,v)=P(a^{\prime},v)$. Then, by Equation 1,
$P(a,v^{\prime})=P(a^{\prime},v^{\prime})$, so the outports chosen by the
agent depend only on states of vertices (the agent does not use its internal
state). Hence this algorithm is equivalent to Rotor-Router on vertices with
degree $2$ and requires $\Omega(n^{2})$ steps to explore the path, starting
from a vertex in the middle of the path (at distance at least $\lfloor
n/2\rfloor$ from each endpoint).
Case B: $P(a,v)\neq P(a^{\prime},v)$. Again from Equation 1 we attain
$P(a^{\prime},v)=P(a,v^{\prime})$ and $P(a,v)=P(a^{\prime},v^{\prime})$. Let
us think about an equivalence relation, where
$W:=(a,v)\equiv(a^{\prime},v^{\prime})$ and
$W^{\prime}:=(a,v^{\prime})\equiv(a^{\prime},v)$. Note that the outports of
$W$ and $W^{\prime}$ are different. Moreover, since the agent changes its
internal state at each step, then after an even number of steps on nodes with
degree $2$, the agent is always in the same state. Consider an agent starting
in the middle of the path and analyze its walk until it reaches some of the
endpoints. Between successive visits to any of the vertices $x$, the agent
makes an even number of steps, hence the agent always visits $x$ in the same
state, but each time the state of the vertex $x$ changes to opposite. Thus
upon consecutive visits, it chooses different outports. Hence the walk
performed by the agent is equivalent to Rotor-Router and for some
initialization of port labels it takes $\Omega(n^{2})$ steps to reach any
endpoint of the path.

We obtained a contradiction in both cases, which proves that
$R_{2}(a^{\prime},w^{\prime})=(a^{\prime},w)$. ∎

The following lemma shows that the agent changes the state of the vertex in
each step at a node of degree $2$.

######  Lemma 6.

$(\forall\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;V(a,v)=v^{\prime}$.

###### Proof.

Assume, that the algorithm does not satisfy the claim, so consider such
$a\in\mathrm{As},\ v\in\mathrm{Vs}$, that $V(a,v)=v$ and denote $P(a,v)=p$.
Then from Fact 2 we get $R_{2}(a,v)=(a^{\prime},v)$. Moreover from Fact 4,
$R_{2}(a^{\prime},v)\neq(a,v)$ and again from Fact 2,
$R_{2}(a^{\prime},v)\neq(a^{\prime},v)$, hence $V(a^{\prime},v)=v^{\prime}$.

We consider two cases:
Case A: $R_{2}(a^{\prime},v)=(a^{\prime},v^{\prime})$. Observe that in this
case from Lemma 3 we obtain $A(a^{\prime},v)\neq A(a^{\prime},v^{\prime})=a$.
Moreover, if $q=P(a^{\prime},v)\neq P(a^{\prime},v^{\prime})=q^{\prime}$, then
the agent falls into infinite loop on the following gadget:

$v$ $*$ $*$ $v$ $p$$q$$q^{\prime}$$p^{\prime}$$p$$q$$q^{\prime}$$p^{\prime}$

If the starting state of the agent is $a$, then the adversary chooses the
starting position as the leftmost node and if it is $a^{\prime}$, then of the
middle nodes. Observe that if agent is in one of the outer vertices in state
$a$, the agent changes its state to $a^{\prime}$ and moves via port $p$ to one
of the two vertices in the middle. Since
$R_{3}(a^{\prime},v)=(a^{\prime},v^{\prime},q)$ and
$R_{3}(a^{\prime},v^{\prime})=(a,\ast,q^{\prime})$ ($\ast$ takes any possible
value), the next time the agent enters to the outer vertex (via port
$q^{\prime}$) will be in state $a$. And since $R_{2}(a,v)=(a^{\prime},v)$ the
states of both outer vertices remain $v$. This means that the agent cannot
escape from such a gadget.

Therefore $P(a^{\prime},v)=P(a^{\prime},v^{\prime})$. From Lemma 4 and Fact 2
we obtain that $R_{2}(a,v^{\prime})=(a,v)$ and
$P(a^{\prime},v)=P(a^{\prime},v^{\prime})\neq P(a,v^{\prime})$.

If we had $R_{2}(a^{\prime},v^{\prime})=(a,v^{\prime})$, then by Lemma 3,
$A(a,v)\neq A(a,v^{\prime})=a$, hence, from Fact 2,
$R_{2}(a,v^{\prime})=(a,v)$. By the symmetry, we conclude that
$P(a,v)=P(a,v^{\prime})\neq P(a^{\prime},v)=P(a^{\prime},v^{\prime})$, hence
ports depend only on the agent‘s state, so we obtain the following algorithm,
with simple counterexamples:

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$
$p$$p$$p^{\prime}$$p^{\prime}$

$v^{\prime}$ $a$ $v$ $p^{\prime}$$p$$p$$p^{\prime}$ $v$ $a^{\prime}$
$v^{\prime}$ $p$$p^{\prime}$$p^{\prime}$$p$

On the other hand, if $R_{2}(a^{\prime},v^{\prime})\neq(a,v^{\prime})$, then
by Fact 2 we obtain $V(a^{\prime},v^{\prime})=v$. Recall that
$A(a^{\prime},v^{\prime})=a$, so $R_{2}(a^{\prime},v^{\prime})=(a,v)$.
Moreover, from Lemma 4, we get that $A(a,v^{\prime})=a$, because
$A(a,v)=a^{\prime}$. From Fact 2 we attain $R_{2}(a,v^{\prime})=(a,v)$.

Now, if additionally $P(a,v^{\prime})=p$, then from
$P(a^{\prime},v)=P(a^{\prime},v^{\prime})\neq P(a,v^{\prime})$ we obtain
$R_{3}(a^{\prime},v^{\prime})=(a,v,p^{\prime})$ and
$R_{3}(a^{\prime},v)=(a^{\prime},v^{\prime},p^{\prime})$, so we end up with
the following algorithm and we present two gadgets for it:

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$
$p$$p$$p^{\prime}$$p^{\prime}$

$v$ $a$ $v$ $v$ $v$
$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$ $v^{\prime}$
$a^{\prime}$ $v$ $v$ $v$ $v$
$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$

On the other hand, if alternatively $P(a,v^{\prime})=p^{\prime}$, then we
similarly obtain $R_{3}(a^{\prime},v^{\prime})=(a,v,p)$ and
$R_{3}(a^{\prime},v)=(a^{\prime},v^{\prime},p)$ and the provided algorithm
falls into infinite loop on the following gadgets:

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$
$p^{\prime}$$p$$p$$p$

$v$ $a^{\prime}$ $v$ $v$ $v$
$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$ $v$ $a$ $v$ $v$
$v$ $v$
$p$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p^{\prime}$

This completes the analysis of Case A.
Case B: $R_{2}(a^{\prime},v)=(a,v^{\prime})$. From Lemma 3,
$A(a^{\prime},v)\neq A(a^{\prime},v^{\prime})=a^{\prime}$, so
$R_{2}(a^{\prime},v^{\prime})=(a^{\prime},v)$, due to Fact 2. If we had
$R_{2}(a,v^{\prime})=(a^{\prime},v^{\prime})$, then by symmetry we could swap
$v$ with $v^{\prime}$ and obtain Case A. Hence
$R_{2}(a,v^{\prime})\neq(a^{\prime},v^{\prime})$. Again, Fact 2 bears
$V(a,v^{\prime})=v$.

Suppose that $P(a^{\prime},v)=P(a^{\prime},v^{\prime})=p^{\prime}$. Then
$P(a,v^{\prime})=p$ and $A(a,v^{\prime})=a$ from Lemma 4, so
$R_{3}(a,v^{\prime})=(a,v,p)$, what provides Algorithm Q from Section 5, which
can be looped by the adversary. Thence we assume that either
$P(a^{\prime},v)\neq p^{\prime}$ or $P(a^{\prime},v^{\prime})\neq p^{\prime}$.
Moreover, let us denote $P(a^{\prime},v^{\prime})=q$. Consider the following
gadget (if the agent starts in state $a$ it is initialized on one of the outer
vertices and otherwise on one of the inner vertices, what is indicated above
the nodes):

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$ $p$$p$$q$

$v$ $a$ $v$ $a^{\prime}$ $v$ $a^{\prime}$ $v$
$a$$p$$q$$q^{\prime}$$p$$q$$q^{\prime}$

Consider the following three invariants:

  * I1

While the agent visits one of the inner vertices in state $a$, then the state
of this vertex is always $v$.

  * I2

The agent visits the outer vertices always in state $a$.

  * I3

The state of the outer vertices is always $v$.

Notice, that as long as the invariants are not violated, the agent cannot
escape the gadget because it always exits via port $q^{\prime}$ from the outer
vertices. Observe, that the invariants are initially true and assume that all
three invariants were true up to some step $t$. We want to show that the
invariants will remain true after this step.

First, we show that the agent cannot violate I3 in step $t+1$. In order to do
so, it need to change the state of an outer vertex from $v$ to $v^{\prime}$,
so it has to visit this vertex in state $a^{\prime}$ while entering to the
vertex via port $q^{\prime}$. Therefore, at the moment $t$, the agent should
have internal state $a$, so since the invariant I1 was not violated, the
appropriate vertex had state $v$. In consequence, $P(a,v)=q^{\prime}$, hence
$q=p^{\prime}$. From the assumption, $P(a^{\prime},v)=p$. Note that the
internal state of the agent cannot be changed to $a$ during the step $t-1$,
from outer node to inner node, because it either violates I2 or I3. Therefore
such the move should be between two inner nodes, via port $q$.

Hence, from invariant I1, we may conclude that $P(a^{\prime},v)=q=p^{\prime}$,
contrary to previous observation. The same argument shows that the agent also
cannot violate I2 in step $t+1$.

As long as invariants I2 and I3 are not violated, the agent always enters to
inner vertices from outer vertices in state $a^{\prime}$. Thence, in order to
violate I1, the state of the agent has to be changed to $a$ during the pass
between the middle nodes (via port $q$), so
$R_{3}(a^{\prime},v)=(a,v^{\prime},q)$ (otherwise the agent had to violate I1
before). Then, from the assumption, $q$ cannot be $p^{\prime}$, so from Lemma
4, $P(a,v^{\prime})=p^{\prime}$. However, then the only way to go to outer
node is via port $p^{\prime}$, but then the agent violates I1. Hence the agent
cannot violate any of the invariants hence it cannot escape the gadget. This
completes the proof of Case B. ∎

Algorithms $X$ and $Y$ Consider the following two algorithms:

Algorithm $X$ $a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$
$v^{\prime}$ $p$$p^{\prime}$$p$$p^{\prime}$

Algorithm $Y$ $a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$
$v^{\prime}$ $p$$p^{\prime}$$p$$p^{\prime}$

######  Lemma 7.

Algorithms $X$ and $Y$ require time $\Omega(n^{2})$ to explore a path.

###### Proof.

Observe that in both algorithms X and Y, the state of the agent determines the
outport chosen by the agent (because $P(a,\ast)=p$ and
$P(a^{\prime},\ast)=p^{\prime}$). Moreover, the following property also holds
for both algorithms:

$(\forall\;v\in\mathrm{Vs})(\forall\;a\in\mathrm{As})(\exists\;b\in\mathrm{As})\;R_{2}(a,v)=(b,v^{\prime})\land
R_{2}(a,v^{\prime})=(b^{\prime},v)~{}.$ (2)

Fix any algorithm $\mathcal{A}$ satisfying both aforementioned properties. Fix
some arbitrary orientation of the line, where each port points either to the
left or to the right. Endpoints of the line are its leftmost and rightmost
nodes. The starting position of the agent is chosen as a node at distance at
least $\lfloor n/2\rfloor$ from both endpoints of the line. We will show that
for $\mathcal{A}$, for such initial position, for some initialization of port
labels, the agent will perform a walk with the following pattern: two steps in
some particullar direction interleaved with one step in the opposite
direction. Moreover, after discovering a new node (i.e., visiting a node for
the first time) the agent will reverse the direction of its walk. It is easy
to see that such a walk needs $\Omega(n^{2})$ steps to visit all the nodes.

We will show, that the adversary is able to force the agent to move according
to a sequence that can be decomposed into blocks LR, RL, LRL and RLR where L
denotes a move via port pointing to the left and R — a move through the port
pointing to the right. The adversary will define the port labels and initial
states of nodes upon the first visits of the agent to these nodes.

In the first claim, we will show that when the agent visits a new node for the
first time, it performs RL (or LR) block and reverses the direction of its
walk. In this case we define the initialization of each newly discovered node
upon the first visit of the agent at this node. It can be decoded into an
explicit construction of a path initialization, different for algorithms X and
Y. In the second claim we will show that when the agent visits a previously
visited node, it performs RLR (or LRL) block and does not reverse the
direction of its walk.

Claim 1. When the agent visits a node $\beta$ for the first time with R-move
(L-move) from node $\alpha$, the two consecutive steps (the step to node
$\beta$ and the following step) is a RL (LR) block. The next block starts with
L-move (R-move) from node $\alpha$.

Assume, that the move to node $\beta$ is a R-move (the case of L-move is
symmetric). Consider a situation that the agent uses R-move with a state
$(b,w)$ and enters to $\beta$, with some agent state $c$. The vertex state of
node $\alpha$ is then $w^{\prime}$ (by (2)). The next move will be performed
via port determined by $c$. Let us denote $p=P(c,\ast)$). The adversary
defines the left outport of the newly discovered node $\beta$ as $p$. Since
the agent state determines the outport and the adversary wants the agent to
perform L-move again, so the next time the agent will be in $\alpha$, it
should have the opposite agent state, i.e. $b^{\prime}$. By (2), there exists
such $u$ that $R_{2}(c,u)=(b^{\prime},u^{\prime})$. Therefore, the adversary
defines the initial state of $\beta$ as $u$. Hence the agent will perform a RL
block. After the block, the agent is back in node $\alpha$ and its internal
state is $b^{\prime}$, hence the next step will be a L-move. This completes
the proof of Claim 1.

$w$ $b$ $u$ $q$$p$

$w^{\prime}$ $u$ $c$$q$$p$

$w^{\prime}$ $b^{\prime}$ $u^{\prime}$ $q$$p$

Figure 3: Visualisation of consecutive steps of RL-block. Double circles
denote the starting node and actual positions of the agent after each of the
next two steps. Letters above the double circles indicates the actual internal
states.

Claim 2. When the agent is in a node $\beta$ not for the first time after the
first step of RLR-block (LRL-block), then the next block starts with R-move
(L-move).

We will investigate only RLR-block case (the second one is symmetric). Assume
that at the beginning of step $t^{\ast}$, before RLR-block is preformed, we
have the visit to this node):

$w$ $b$ $u$ $c$$q$$r^{\prime}$$r$

Note that the agent state determines the outport, hence in order to perform
RLR-block, the agent state has to be the same upon its both visits to the
leftmost node. During RLR-block, the state of the leftmost vertex is flipped
twice (by (2)), hence its state after the execution of the block is identical
to its state before the progress. Note that the move from the rightmost node
during the step $t^{\ast}+1$ changes the state of the rightmost vertex.
Realize that the last visit (before $t^{\ast}$) in the rightmost node was
performed with the agent state $c$ and was followed by a L-move, so the state
of the agent at the beginning of step $t^{\ast}+1$ is $c$. We want the agent
state to change to $c^{\prime}$ during step $t^{\ast}+2$. From (2), there
exists $v$ such that $A(b,v)=c^{\prime}$, so $v=w^{\prime}$. Therefore the
situation after step $t^{\ast}+2$ is the following:

$w$ $b$ $u^{\prime}$ $c^{\prime}$$q$$r^{\prime}$$r$

Since the agent state determines the outport and $P(c,\ast)=r$, thus
$P(c^{\prime},\ast)=r^{\prime}$, which means that the next block starts with
R-move.

Claim 3. When the agent visits a node $\beta$ not for the first time with
R-move (L-move) from node $\alpha$ after the, the three consecutive steps (the
step to node $\beta$ and two following steps) is a RLR (LRL) block.

We will prove this claim by induction. Consider the earliest time step
$t^{\ast}>4$, when the first part of the claim does not hold (observe that
first two blocks are always LR and RL in some order, hence we do not lose
generality). Assume that Claim 3 holds in all steps prior to $t^{\ast}$ and at
the beginning of step $t^{\ast}$ we have the following situation:

$w$ $b$ $u$ $c$$q$$r^{\prime}$$r$

Suppose that the agent wants to take two consecutive R-moves (the case of two
consecutive L-moves is symmetric) during steps $t^{\ast}$ and $t^{\ast}+1$. By
the assumption of this claim, the first R-move during step $t^{\ast}$ is to a
node that has been visited before $t^{\ast}$. Since R-move begins a new block
and $t^{\ast}$ is the earliest time when this claim does not hold, then by
Claim 2, the last move had to be R as well, so the previous block ended with
sequence LR (either LR-block or RLR-block was used). Moreover after the last
visit to the rightmost node, the agent moved to the leftmost node, hence
$P(c,\ast)=r$ and $P(c^{\prime},\ast)=r^{\prime}$, thus since the agent is
about to perform two consecutive R-moves, then $A(b,w)=c^{\prime}$. Using the
argument as in proofs of Claim 1, Claim 2, at the beginning of step
$t^{\ast}-2$ the situation looked as follows:

$y$ $e$ $w^{\prime}$ $b^{\prime}$ $u$ $c$$t$$q$$r^{\prime}$$r$$q^{\prime}$

The last change of the state of the highlighted node was during step
$t^{\ast}-2$. Note that at the end of step $t^{\ast}-2$, the leftmost node was
visited. Moreover, the node $(c,u)$ was visited before this step (otherwise
the agent cannot perform the double R-move in steps $t^{\ast}$ and
$t^{\ast}+1$ due to Claim 1). Therefore, let a step $s^{\ast}$ be the last
moment, when the node $(b,w)$ was visited from the node $(c,u)$ before the
step $t^{\ast}-2$. Note that thence during steps $s^{\ast}$ and $s^{\ast}+1$,
the agent went left, so at $s^{\ast}$ the last move of a block ended by the
sequence RL was performed.

If this block was LRL, then during the step $s^{\ast}-2$, the agent has to go
left, so since $P(c,\ast)=r$, the internal state is then $c$. However, from
the previous argument about the changes of states during LRL-block, we can
obtain a situation presented on the left of Figure 4 at the moment
$s^{\ast}-2$.

Otherwise, the RL-block was performed during steps $s^{\ast}-1$ and $s^{\ast}$
and the situation before the step $s^{\ast}-1$ is given on the right of Figure
4.

$w$ $b$ $u^{\prime}$ $c^{\prime}$$q$$r$

$w$ $b$ $u^{\prime}$ $q$$r$

Figure 4: A case of situation before LRL-block at the moment $s^{\ast}-2$ is
presented on the left. A case before RL-block at the moment $s^{\ast}-1$ is
given on the right

Therefore $A(b,w)=c$ (because $P(c,\ast)=r$), what is contrary to previously
obtained $A(b,w)=c^{\prime}$. A symmetric situation holds if the agent wants
to start a new block by LL.

Now we would like to estimate the number of moves needed to explore the graph
by this algorithm. Realize that after RL-block, LRL-block is repeated until
the next new node is found by LR-block. Symmetrically with swapped R and L.
Let say that the line has $n$ nodes. Then the adversary may put the agent in
the middle of the line in such the way that, so the agent has to performs
$n-2$ RL-blocks or LR-blocks. After every RL-block (or LR-block), there is one
more visited node, so the number of RLR-blocks (or LRL-blocks) that has to be
executed before performing the next RL-block (or LR-block) increases by $1$.
The last number of consecutive LRL-blocks or RLR-blocks is $n-2$ (because the
last move is a single one), so the agent has to perform at least

$2(n-2)+1+\sum\limits_{i=1}^{n-2}3i=\frac{(n-2)(3n+1)}{2}+1=\Omega(n^{2})$

moves in order to explore the graph. It worths to note that it is
approximately $3$ times longer than Rotor-Router algorithm. ∎

######  Lemma 8.

Assume that we have:

  1. 1.

$(\forall\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;V(a,v)=v^{\prime}$,

  2. 2.

function $P$ satisfies $P(s)=P(s^{\prime})=P(s^{\prime\prime})$ for three
different state values $s,s^{\prime},s^{\prime\prime}\in S$.

Then an algorithm requires in the worst case $\Omega(n^{2})$ steps to explore
a path.

###### Proof.

Set $S$ has $4$ possible values, so if function $P$ returns the same port for
all of them then the algorithm trivially cannot explore all paths of length
$>2$.

Assume that for some $a\in\mathrm{As}$, $v\in\mathrm{Vs}$ and
$p\in\mathrm{Ps}$, we have $P(a,v)=p$ and $P(s)=p^{\prime}$ for all
$s\neq(a,v)$. Let us construct a path $\mathcal{P}=(v_{1},v_{2},\dots,v_{n})$
of length $n$ such that a port from $v_{i}$ to $v_{i+1}$ is always $p$ (and
port from $v_{i}$ to $v_{i-1}$ is $p^{\prime}$). Let $v_{1}$ be the starting
position of the agent and $v^{\prime}$ be the initial state of each vertex.
Consider the exploration time of such the algorithm on $\mathcal{P}$.

To prove the time complexity, we show the following:
Claim: For any $i\in\\{2,3,\dots n-1\\}$, the agent visits node $v_{1}$
between first visits to $v_{i}$ and $v_{i+1}$.
To prove the claim observe that, when entering $v_{i}$ for the first time, the
last exit from each vertex $v_{2},v_{3},\dots,v_{i-1}$ was via port $p$. This
means that the state of each of these nodes is $v^{\prime}$ (it is because
$V(a,v)=v^{\prime}$ by (1)). Since the states of $v_{i},v_{i-1},\dots,v_{2}$
are $v^{\prime}$, and the agent is at $v_{i}$, it leaves each of these
vertices via port $p^{\prime}$ and walks straight to node $v_{1}$. This
completes the proof of the claim.

The lemma is a direct consequence of the claim, because time to explore the
whole path is at least $2\cdot\sum_{i=1}^{n-2}i\in\Omega(n^{2})$. ∎

We are ready to complete the proof of Theorem 3

###### Proof of Theorem 3.

From Lemma 5 we know that the state of the agent is not changed during every
step at the nodes with degree $2$. By Lemma 6 the state of a vertex is flipped
by the agent upon each visit to the vertex. If the outport chosen by the agent
is determined solely based on the state of the vertex then such algorithm
would be equivalent to Rotor-Router (on vertices with degree $2$) hence would
require time $\Omega(n^{2})$. By Lemma 8, if function $P$ doe not take each of
two ports in two different states $s\in S$, then the adversary may choose an
arrangement in which the agent has to perform $\Omega(n^{2})$ steps to explore
the path. Consider the remaining possible algorithms.

Case A. Assume that the outport is defined by the state of the agent i.e.

$(\exists\;p\in\mathrm{Ps})(\forall\;v\in\mathrm{Vs})\;P(a,v)=p\land
P(a^{\prime},v)=p^{\prime}~{}.$ (3)

By Lemma 5, we know that there exists a state for which the agent does not
change its internal state. Denote such state by $(a,v)$. Then by (3),
$R_{3}(a,v)=(a,v^{\prime},p)$ and because of Fact 4 and Lemma 6, we obtain
$R_{3}(a,v^{\prime})=(a^{\prime},v,p)$.

If we had $A(a^{\prime},v)=a^{\prime}$, then similarly
$R_{3}(a^{\prime},v)=(a^{\prime},v^{\prime},p^{\prime})$ and
$R_{3}(a^{\prime},v^{\prime})=(a,v,p^{\prime})$, what bears Algorithm X that
requires $\Omega(n^{2})$ steps by Lemma 7.

Hence, suppose that $A(a^{\prime},v)=a$, so
$R_{3}(a^{\prime},v)=(a,v^{\prime},p^{\prime})$ (by Fact 4 and Lemma 6 once
again).

If moreover $A(a^{\prime},v^{\prime})=a^{\prime}$, then similar argument gives
$R_{3}(a^{\prime},v^{\prime})=(a^{\prime},v,p^{\prime})$. Therefore we
obtained Algorithm Y that also requires $\Omega(n^{2})$ steps by Lemma 7.

Hence $A(a^{\prime},v^{\prime})=a$ and
$R_{3}(a^{\prime},v^{\prime})=(a,v,p^{\prime})$. The obtained algorithm
satisfies (3), so when the agent is walking on nodes with degree $2$, it
cannot choose port $p^{\prime}$ twice in a row, thus it cannot traverse from
left to right the following gadget:

$\ast$ $\ast$ $\ast$ $\ast$
$p$$p^{\prime}$$p^{\prime}$$p^{\prime}$$p$$p$$p$${}^{\prime}p$

This completes the analysis of Case A.

Case B. Now assume that

$(\forall\;p\in\mathrm{Ps})(\forall\;a\in\mathrm{As})(\exists\;v\in\mathrm{Vs})\;P(a,v)=p~{}.$
(4)

Due to Fact 1 we may assume without a loss of generality that
$R_{3}(a,v)=(a^{\prime},v^{\prime},p)$. Assume that
$A(a^{\prime},v)=a^{\prime}$. Since the vertex state does not determine the
outport Lemma 6 and (4), we get
$R_{3}(a^{\prime},v)=(a^{\prime},v^{\prime},p^{\prime})$. Then also
$R_{3}(a^{\prime},v^{\prime})=(a,v,p)$, because of Lemma 6, (4) and Fact 4.
Moreover, the agent state is not determined by the vertex state, so again from
(4), we get $R_{3}(a,v^{\prime})=(a^{\prime},v,p^{\prime})$. The obtained
algorithm (call it Algorithm Z) is incorrect due to the following
counterexample:

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$
$p$$p^{\prime}$$p^{\prime}$$p$

$v$ $a^{\prime}$ $v^{\prime}$ $v$ $v^{\prime}$ $v^{\prime}$ $v$
$p^{\prime}$$p^{\prime}$$p^{\prime}$$p$$p$$p$$p^{\prime}$$p^{\prime}$$p^{\prime}$$p$$p$$p$
$v^{\prime}$ $a$ $v$ $v$ $v^{\prime}$ $v^{\prime}$ $v$
$p^{\prime}$$p^{\prime}$$p^{\prime}$$p$$p$$p$$p^{\prime}$$p^{\prime}$$p^{\prime}$$p$$p$$p$

On the other hand if we have $A(a^{\prime},v)=a$, then
$R_{3}(a^{\prime},v)=(a,v^{\prime},p^{\prime})$ from Lemma 6 and (4).

If moreover $A(a^{\prime},v^{\prime})=a$, then the same argument gives
$R_{3}(a^{\prime},v^{\prime})=(a,v,p)$. However, if we swap $v$ with
$v^{\prime}$, then we obtain exactly Algorithm Z, which we know is incorrect.

Hence from (4), $R_{3}(a^{\prime},v^{\prime})=(a^{\prime},v,p)$. Note that if
we had $A(a,v^{\prime})=a$, then $R_{3}(a,v^{\prime})=(a,v,p^{\prime})$ by
similar argument, what bears algorithm would be equivalent to Algorithm X (it
is sufficient to flip the vertex states and the ports). Thence
$A(a,v^{\prime})=a^{\prime}$, so together with Lemma 6 and (4) we get
$R_{3}(a,v^{\prime})=(a^{\prime},v,p^{\prime})$ and we obtain the following
Algorithm R:

$a$ $v$ $a^{\prime}$ $v$ $a$ $v^{\prime}$ $a^{\prime}$ $v^{\prime}$
$p^{\prime}$$p$$p^{\prime}$$p$

Observe that Algorithm R has the following property. After taking port $p$,
the agent is always in state $a^{\prime}$ and after taking port $p$, the agent
is always in state $a$. Using this property (and Lemma 6), we will show that
Algorithm Z is equivalent to Rotor-Router. Indeed, let us organize port
numbers on the path in the following pattern, where both incoming arcs to each
node have the same port label:

$\ast$ $\ast$ $\ast$ $\ast$ $\ast$ $\ast$
$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p$$p^{\prime}$$p$$p^{\prime}$$p$$p^{\prime}$

After such initialization of the port labels, we know that upon each visit to
a vertex of degree $2$ the agent is in the same state. Note that this holds
for all nodes of degree $2$, except the nodes that have one of the endpoints
of the path as its neighbors. But except four nodes (endpoints of the path and
theirs neighbors), the algorithm behaves like Rotor-Router, which means that
it chooses a different outport upon every visit to that node. By choosing an
appropriate initialization of vertex states, we can guarantee that the
exploration time of Algorithm R is asymptotically the same as the worst-case
exploration using Rotor-Router, which is $\Omega(n^{2})$ [2]. This completes
the analysis of Case B.

Case C. Assume that

$(\exists\;p\in\mathrm{Ps})(\exists\;a\in\mathrm{As})(\forall\;v\in\mathrm{Vs})\;P(a,v)=p~{}.$

Agent states do not determine the outports and vertex states always change, so
Lemma 4 guarantees the assumptions of Lemma 8 and hence in this case, the
algorithm requires $\Omega(n^{2})$ steps to explore a path.

By exhausting all possible cases, we obtain a contradiction with the
assumption, that there exists an algorithm with time complexity $o(n^{2})$,
which completes the proof of Theorem 3. ∎

##  6 Conclusions and open problems

One conclusion from our paper is that certain assumptions of the model of
mobile agents can be exchanged. We showed, that in the context of linear time
tree exploration, the assumption of clean memory at the nodes can be exchanged
for a single token or the knowledge of the incoming port. The paper leaves a
number of promising open directions. We showed that token and clean memory
allow linear time exploration of trees, however, we have not ruled out the
possibility that linear time exploration of trees is feasible without both
these assumptions. Our lower bound suggests that memory $\omega(1)$ at the
agent is probably necessary in DirtyMem model. Another open direction would be
to consider different graph classes, or perhaps directed graphs. Finally, a
very interesting future direction is to study dual-memory exploration with
team of multiple mobile agents. Such approach could lead to even smaller
exploration time, however, dividing the work between the agents in such models
is very challenging since the graph is initially unknown.

## References

  * [1] R. Aleliunas, R. M. Karp, R. J. Lipton, L. Lovász, and C. Rackoff.  Random walks, universal traversal sequences, and the complexity of maze problems.  In 20th Annual Symposium on Foundations of Computer Science, San Juan, Puerto Rico, 29-31 October 1979, pages 218–223. IEEE Computer Society, 1979.
  * [2] E. Bampas, L. Gasieniec, N. Hanusse, D. Ilcinkas, R. Klasing, A. Kosowski, and T. Radzik.  Robustness of the rotor-router mechanism.  Algorithmica, 78(3):869–895, 2017.
  * [3] M. Bender and D. Slonim.  The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs.  In Proceedings 35th Annual Symposium on Foundations of Computer Science, 1994.
  * [4] M. A. Bender, A. Fernández, D. Ron, A. Sahai, and S. P. Vadhan.  The power of a pebble: Exploring and mapping directed graphs.  Inf. Comput., 176(1):1–21, 2002.
  * [5] P. Berenbrink, C. Cooper, and T. Friedetzky.  Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time.  Random Struct. Algorithms, 46(1):36–54, 2015.
  * [6] R. Cohen, P. Fraigniaud, D. Ilcinkas, A. Korman, and D. Peleg.  Label-Guided Graph Exploration by a Finite Automaton.  ACM Trans. Algorithms, 4(4):42:1–42:18, Aug. 2008.
  * [7] H. Dai and K. E. Flannery.  Improved length lower bounds for reflecting sequences.  In International Computing and Combinatorics Conference, pages 56–67. Springer, 1996.
  * [8] D. Dereniowski, Y. Disser, A. Kosowski, D. Pajak, and P. Uznanski.  Fast collaborative graph exploration.  Inf. Comput., 243:37–49, 2015.
  * [9] D. Dereniowski, A. Kosowski, D. Pajak, and P. Uznanski.  Bounds on the cover time of parallel rotor walks.  J. Comput. Syst. Sci., 82(5):802–816, 2016.
  * [10] K. Diks, P. Fraigniaud, E. Kranakis, and A. Pelc.  Tree exploration with little memory.  J. Algorithms, 51(1):38–63, 2004.
  * [11] K. Efremenko and O. Reingold.  How well do random walks parallelize?  In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 12th International Workshop, APPROX 2009, and 13th International Workshop, RANDOM 2009, Berkeley, CA, USA, August 21-23, 2009\. Proceedings, volume 5687 of Lecture Notes in Computer Science, pages 476–489. Springer, 2009.
  * [12] R. Elsässer and T. Sauerwald.  Tight bounds for the cover time of multiple random walks.  Theor. Comput. Sci., 412(24):2623–2641, 2011.
  * [13] U. Feige.  A tight lower bound on the cover time for random walks on graphs.  Random Struct. Algorithms, 6(4):433–438, 1995.
  * [14] U. Feige.  A tight upper bound on the cover time for random walks on graphs.  Random Struct. Algorithms, 6(1):51–54, 1995.
  * [15] P. Fraigniaud, L. Gasieniec, D. R. Kowalski, and A. Pelc.  Collective tree exploration.  Networks, 48(3):166–177, 2006.
  * [16] P. Fraigniaud and D. Ilcinkas.  Digraphs exploration with little memory.  In STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings, volume 2996 of Lecture Notes in Computer Science, pages 246–257. Springer, 2004.
  * [17] P. Fraigniaud, D. Ilcinkas, G. Peer, A. Pelc, and D. Peleg.  Graph exploration by a finite automaton.  Theor. Comput. Sci., 345(2-3):331–344, 2005.
  * [18] P. Fraigniaud, D. Ilcinkas, S. Rajsbaum, and S. Tixeuil.  Space lower bounds for graph exploration via reduced automata.  In Structural Information and Communication Complexity, 12th International Colloquium, SIROCCO 2005, Mont Saint-Michel, France, May 24-26, 2005, Proceedings, volume 3499 of Lecture Notes in Computer Science, pages 140–154. Springer, 2005.
  * [19] L. Gasieniec and T. Radzik.  Memory efficient anonymous graph exploration.  In Graph-Theoretic Concepts in Computer Science, 34th International Workshop, WG 2008, Durham, UK, June 30 - July 2, 2008. Revised Papers, volume 5344 of Lecture Notes in Computer Science, pages 14–29, 2008.
  * [20] R. Klasing, A. Kosowski, D. Pajak, and T. Sauerwald.  The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks.  Distributed Comput., 30(2):127–148, 2017.
  * [21] A. Kosowski.  A _Õ_ (_n ${}^{\mbox{2}}$_) time-space trade-off for undirected _s-t_ connectivity.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1873–1883. SIAM, 2013.
  * [22] A. Kosowski and D. Pajak.  Does adding more agents make a difference? A case study of cover time for the rotor-router.  J. Comput. Syst. Sci., 106:80–93, 2019.
  * [23] M. Koucký.  Log-space constructible universal traversal sequences for cycles of length o(n${}^{\mbox{4.03}}$).  Theor. Comput. Sci., 296(1):117–144, 2003.
  * [24] L. Lovász.  Random walks on graphs.  Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
  * [25] A. Menc, D. Pajak, and P. Uznanski.  Time and space optimality of rotor-router graph exploration.  Inf. Process. Lett., 127:17–20, 2017.
  * [26] Y. Nonaka, H. Ono, K. Sadakane, and M. Yamashita.  The hitting and cover times of metropolis walks.  Theor. Comput. Sci., 411(16-18):1889–1894, 2010.
  * [27] C. Ortolf and C. Schindelhauer.  A recursive approach to multi-robot exploration of trees.  In Structural Information and Communication Complexity - 21st International Colloquium, SIROCCO 2014, Takayama, Japan, July 23-25, 2014. Proceedings, volume 8576 of Lecture Notes in Computer Science, pages 343–354. Springer, 2014.
  * [28] H. A. Rollik.  Automaten in planaren graphen.  Acta Inf., 13(3):287–298, Mar. 1980.
  * [29] Y. Sudo, F. Ooshita, and S. Kamei.  Self-stabilizing graph exploration by a single agent.  CoRR, abs/2010.08929, 2020.
  * [30] V. Yanovski, I. A. Wagner, and A. M. Bruckstein.  A distributed ant algorithm for efficiently patrolling a network.  Algorithmica, 37(3):165–186, 2003.