# Deciding Graph Property by Single Mobile Agent:
One-Bit Memory Suffices111A part of this paper was presented in the 2018 ACM
Symposium on Principles of Distributed Computing (PODC2018) as a brief
announcement.

Taisuke Izumi222Graduate School of Information Science and Technology, Osaka
University, E-mail: {t-izumi, n-kitamura<EMAIL_ADDRESS>Kazuki
Kakizawa333Graduate School of Engineering, Nagoya Institute of Technology,
E-mail: {kezawa0612<EMAIL_ADDRESS>Yuya Kawabata33footnotemark: 3 Naoki
Kitamura22footnotemark: 2 Toshimitsu Masuzawa22footnotemark: 2

###### Abstract

We investigate the computational power of the deterministic single-agent model
where the agent and each node are equipped with a limited amount of persistent
memory. Tasks are formalized as decision problems on properties of input
graphs, i.e., the task is defined as a subset $\mathcal{T}$ of all possible
input graphs, and the agent must decide if the network belongs to
$\mathcal{T}$ or not. We focus on the class of the decision problems which are
solvable in a polynomial number of movements, and polynomial-time local
computation. The contribution of this paper is the computational power of the
very weak system with one-bit agent memory and $O(1)$-bit storage (i.e. node
memory) is equivalent to the one with $O(n)$-bit agent memory and $O(1)$-bit
storage. We also show that the one-bit agent memory is crucial to lead this
equivalence: There exists a decision task which can be solved by the one-bit
memory agent but cannot be solved by the zero-bit memory (i.e., oblivious)
agent. Our result is deduced by the algorithm of simulating the $O(n)$-bit
memory agent by the one-bit memory agent with polynomial-time overhead, which
is developed by two novel technical tools. The first one is a dynamic $s$-$t$
path maintenance mechanism which uses only $O(1)$-bit storage per node. The
second one is a new lexicographically-ordered DFS algorithm for the mobile
agent system with $O(1)$-bit memory and $O(1)$-bit storage per node. These
tools are of independent interest.

##  1 Introduction

###  1.1 Background and Our Result

The _mobile agent_ model is one of the popular computational models in
distributed computing, where autonomous entities (i.e., _agents_) moving in
the input network process some given task. It is recognized as an abstraction
of robot systems, web crawlers, swarm intelligence, and so on. The models of
mobile agents are characterized by several features such as the number of
agents, capability of agents and nodes, faults, and network topology. It is a
central question in the theory of mobile agents to clarify the computational
power of a given model.

In this paper, we investigate the computational power of the deterministic
single-agent model where the agent and nodes are equipped with a limited
amount of persistent memory. Throughout this paper, we refer to the memory
managed by the agent as “memory”, and that managed by each node as “storage”.
The detailed characteristics follow the standard assumptions of mobile agent
systems: The input graph $G$ is _anonymous_ (i.e., there is no unique ID of
nodes) and neighbors of a node is identified by _local port numbers_ assigned
to the edges incident to the node. The agent does not have any prior knowledge
on the network topology. In one time step, the agent performs local
computation, which includes the update of the information stored in its own
memory and the storage at the current node, and decides the neighbor to which
it moves.

We formalize tasks as decision problems on properties of input networks. More
precisely, a task is a subset $\mathcal{T}$ of all possible inputs
$\mathcal{G}$. The agent must decide if the input $G$ belongs to $\mathcal{T}$
or not, i.e., the agent terminates with one-bit output indicating
$G\in\mathcal{T}$ or not. This decision problem is defined in a very general
form and covers many popular graph problems. For example, all the following
problems belong to this class: planarity, bipartiteness, and boundedness of
graph parameters such as diameter and treewidth.

We focus on the class of the decision problems which are solvable by a single
mobile agent in a polynomial number of movements and polynomial-time local
computation. Such a class is a natural analogue of class $P$ in the
centralized computation. Formally, we denote by $\mathsf{P_{AGT}}(g(n),h(n))$
the class of the decision problems which are solvable in the mobile agent
system with $g(n)$-bit memory and $h(n)$-bit storage. The main contribution of
this paper is to reveal the relationship between function $g(n)$ and the task
solvability. Surprisingly, we show that the magnitude of $g(n)$ does not
matter. Even if $g(n)=1$, the agent can use the asymptotically whole storage
as its own memory. We have the following theorem:

###### Theorem 1

$\mathsf{P_{AGT}}(1,\Theta(1))=\mathsf{P_{AGT}}(\Theta(n),\Theta(1))$444The
asymptotic version of this class $(\mathsf{P_{AGT}}(\Theta(g(n)),\Theta(h(n))$
is defined as the union of $\mathsf{P_{AGT}}(g^{\prime}(n),h^{\prime}(n))$ for
all $g^{\prime}(n)=\Theta(g(n))$ and $h^{\prime}(n)=\Theta(h(n))$. .

It is easy to show that our result is tight with respect to memory size. That
is, the computational powers of the one-bit memory agent and the zero-bit
memory agent (so-called _oblivious_ agent) are not equivalent under the
assumption of $O(1)$-bit storage. The following theorem is obtained as a
corollary of the impossibility result by Cohen et al. [4].

###### Theorem 2

There exists a decision problem $\mathcal{P}$ such that
$\mathcal{P}\not\in\mathsf{P_{AGT}}(0,\Theta(1))$ and
$\mathcal{P}\in\mathsf{P_{AGT}}(1,\Theta(1))$ hold. That is,
$\mathsf{P_{AGT}}(0,\Theta(1))\subsetneq\mathsf{P_{AGT}}(1,\Theta(1))$.

###  1.2 Technical Idea

The proof of Theorem 1 consists of two parts, each of which shows
$\mathsf{P_{AGT}}(O(1),O(1))=\mathsf{P_{AGT}}(O(n),O(1))$ and
$\mathsf{P_{AGT}}(1,O(1))=\mathsf{P_{AGT}}(O(1),O(1))$. The second part of
reducing the agent memory size from $O(1)$ to $1$ is realized by a simple
idea, which disassembles the information transfer caused by the movement of
$k$-bit memory agent into $k$ iterations of round-trip movement of the one-bit
agent. Hence the main technical challenge is at the first part. The key
ingredient of the first part is an algorithm for serializing all the nodes in
the network. The serialized nodes, each of which has $O(1)$-bit storage, can
be treated as the $O(n)$-bit tape $T$ of a Turing machine(TM), and our
simulation algorithm utilizes it as the agent memory. Letting $A$ be any
algorithm utilizing $O(n)$-bit agent memory, we model $A$ (i.e., the algorithm
of the simulated agent) as a Turing machine $M$ utilizing $O(n)$-bit tape, and
the simulation algorithm executes $M$ on tape $T$. The primary hurdle of this
approach is that we cannot explicitly store the serialized order of the nodes.
More generally, $O(1)$-bit storage per node does not suffice to store any
_path structure_ assigning each node with a predecessor neighbor and a
successor neighbor explicitly. The main technical tool of our solution is to
provide a new distributed data structure _R-path_ , which dynamically
maintains a traversable path between two given nodes by spending only
$O(1)$-bit storage per node and $O(1)$-bit memory. Utilizing this technique,
our simulation algorithm implements the lexicographically-ordered depth-first
search (Lex-DFS) for the input network $G$. It obviously provides an implicit
serialization of all nodes following the pre-order of Lex-DFS. When simulating
$M$ using $O(n)$-bit tape, the simulator agent always keeps the state of $M$
in its memory. In addition, a constant number of R-path instances are used to
connect the locations of the simulator agent, simulated agent, and tape head.
Then the agent can freely access the information stored in those locations by
traversing the maintained paths, and can simulate one-step execution of $M$.

Finally, we emphasize that our Lex-DFS algorithm itself is also a by-product
contribution of this paper. To the best of our knowledge, it is the first DFS
algorithm only spending $O(1)$-bit memory and $O(1)$-bit storage per node.
Since Lex-DFS has a wide range of applications, we believe that this tool will
be useful for importing such applications into the mobile agent systems with
limited memory/storage capability.

###  1.3 Related Work

To the best of our knowledge, there exists no prior work on addressing the
space complexity of general tasks in the single-agent model. Nevertheless, the
space complexity of the single-agent model for a specific problem is much
investigated. The mainstream of this research line is the _graph exploration
problem_ , which has a long history and the origin goes back to the Shannon’s
experiment on maze-solving mouse [17]. In the field of theoretical computer
science, it received much attention after the seminal paper by Aleliunas et
al. [2] providing the explicit polynomial-time upper bound of the random walks
in undirected graphs (so-called _cover time_). It implies that a single
$O(\log n)$-bit counter yields a simple randomized graph exploration algorithm
with termination. This result triggers the interest of log-space
_deterministic_ graph exploration algorithms in relation to the computational
complexity issue of log-space computability, and a number of algorithms are
developed [12, 9, 13, 10, 14]. The Reingold’s seminal logspace undirected
connectivity algorithm is one of the milestones on this line [15]. The memory-
size optimality of the Reingold’s algorithm is also shown by Fraigniaud et al.
[8]. The speed matter of graph exploration is considered with respect to time-
space tradeoff [7, 11].

While all the results above assumes the system without storage,
sublogarithmic-memory graph exploration algorithms assuming storage has been
proposed, for a variety of storage models. For example, the _rotor-router_
model [3], which is also known as a technique of de-randomizing random walks,
guides the agent by the pointer managed by each node. This model attains the
graph exploration with zero-bit memory and $O(\log\Delta)$-bit storage, where
$\Delta$ is the maximum degree of the network. Yet another example is the the
pebble-based algorithm proposed by Disser et al. [5], which is a graph
exploration algorithm using $O(\log\log n)$ distinct pebbles. The $k$-pebble
model is one of the restricted versions of the standard storage model, where
each agent has $k$ distinguished pebbles, and can put and pick-up each pebble
on any node for leaving some information there. The conceptual idea of this
algorithm is very close to our result. The algorithm simulates a log-space
Turing machine in a distributed manner using $O(\log\log n)$ pebbles, and runs
the Reingold’s algorithm on the simulated Turing machine. Since this model is
incomparable to our $O(1)$-bit storage model, the technical contribution of
our result is definitely independent of this algorithm. In addition, the
simulation overhead of the algorithm by Disser et al. is unfortunately super-
polynomial, while our result only incurs the polynomial-time overhead. The
polynomial-time graph exploration using $O(1)$-bit memory and $O(1)$-bit
storage has been shown to be solvable by Cohen et al.[4]. The exploration
algorithm presented in that paper is actually the breadth-first search (BFS)
by the agent. Our DFS algorithm complements another side of very standard
graph search algorithms. Note that it is certainly possible to use the
exploration algorithm by Cohen et al. as the building block of our simulation
algorithm for node serialization, instead of our lex-DFS algorithm. However,
no general simulation technique as our result is addressed there. The paper by
Cohen et al.[4] also presents the impossibility of graph exploration by zero-
bit memory agents if the storage size is $o(\log\Delta)$ bits, which is the
basis of the proof of Theorem 2. A variety of the exploration algorithms
attaining different memory/storage complexities are also presented in [16],
but no algorithm there attains the complexity of $O(1)$-bit memory and
$O(1)$-bit storage.

###  1.4 Roadmap

The paper is organized as follows: In Section 2, we introduce the formal model
and the problem definition. Section 3 explains the Lex-DFS algorithm using
$O(1)$-bit memory and $O(1)$-bit storage, as well as the details of the R-path
structure. Following the proof of
$\mathsf{P_{AGT}}(\Theta(1),\Theta(1))=\mathsf{P_{AGT}}(\Theta(1),\Theta(n))$
in Section 4.2, we present the result of
$\mathsf{P_{AGT}}(1,\Theta(1))=\mathsf{P_{AGT}}(\Theta(1),\Theta(1))$ in
Section 4.3. The proof of Theorem 2 is straightforward, and thus it is
deferred to the appendix.

##  2 Preliminaries

###  2.1 Input Graph

We denote by $[a,b]$ the set of integers at least $a$ and at most $b$. The
input graph $G=(V,E,\Pi)$ is a simple undirected connected graph with port
numbering, where $V$ is the set of nodes, $E\subseteq V\times V$ is the set of
edges, $\Pi$ is the set of port-numbering functions (explained later). We
denote by $n$ and $m$ the numbers of nodes and edges respectively. Let $E(v)$
be the set of edges incident to node $v$, $N(v)$ be the set of nodes that are
adjacent to $v$, and $\Delta(v)$ be the degree of node $v\in V$. While each
element $v$ in $V$ is treated as the unique ID of the corresponding node, it
is not identified by the agent. That is, nodes are _anonymous_. For the agent
to distinguish adjacent nodes, a _local port numbering_ is defined for each
node. An edge incident to a vertex $v$ is assigned with a unique label in
$[0,\Delta(v)-1]$ defined by a port numbering function $\pi_{v}\colon
E(v)\to[0,\Delta(v)-1]$. The set $\Pi$ consists of the port-numbering
functions for all nodes in $V$. Note that two port numbers $\pi_{v}(e)$ and
$\pi_{u}(e)$ assigned to the same edge $e=(u,v)$ are independent. Since $E(v)$
and $N(v)$ has one-to-one correspondence, we often abuse $\pi_{v}$ as a
function from $N(v)$. That is, for any $u\in N(v)$, $\pi_{v}(u)$ represents
the $v$’s port number of edge $(v,u)$. Furthermore, we also denote the inverse
function of $\pi_{v}(u)$ on $N(v)$ by $\pi^{-1}_{v}$ (i.e.,
$\pi^{-1}_{v}\colon[0,\Delta(v)-1]\to N(v)$).

###  2.2 Mobile Agent

Each node $v\in V$ has _storage_ , which is a persistent memory keeping
information even after the agent leaves (i.e., the agent can refer to that
information when it comes back). We denote by $b(v)$ the information stored in
the storage at $v\in V$. Since we consider the system with $O(1)$-bit storage
per node, $b(v)$ is treated as a fixed-length bit string. At the beginning of
the execution, $b(v)$ for all $v\in V$ are initialized with the sequence of
zeros. The execution of the agent follows discrete time steps. In each step,
the agent first observes the degree of the current vertex $v$, the port number
of the edge from which it entered $v$, and the storage of $v$. Then it
performs local computation following the algorithm and the observed
information. The local computation outputs the information left to the storage
of the current node and the port number $x\in[0,\Delta(v)-1]$ indicating the
destination of the next movement. Finally, the step finishes with the movement
to $\pi^{-1}_{v}(x)$. It is guaranteed that the movement at a step finishes by
the beginning of the next step. The location of the agent at the current step
is referred to as $v_{\mathrm{cur}}$, and the port number from which the agent
comes to $v_{\mathrm{cur}}$ is referred to as $\pi_{\mathrm{in}}$. Note that
the “current step” implied by notations $v_{\mathrm{cur}}$ and
$\pi_{\mathrm{in}}$ depends on the context.

An algorithm $A$ is formally defined by a 5-tape Turing machine
$M(A)=(Q,\Sigma,\gamma,q_{0},q_{1})$, where $Q$ is the set of states,
$\Sigma=\\{0,1,\sqcup\\}$ is the tape alphabet, $\gamma\colon
Q\times\\{0,1\\}^{5}\to Q\times\\{0,1\\}^{5}\times\\{L,R\\}^{5}$ is the
transition function, $q_{0}$ is the initial state, and $q_{1}$ is the
termination state. In what follows, we refer to an atomic step of TMs as “TM
step”, and refer to the time step of agent executions as “agent step” or
simply ”step” for distinguishing them clearly. That is, one agent step
consists of multiple TM steps of $M(A)$ and the following agent movement after
the termination of $M(A)$. The first tape corresponds to the local persistent
memory of the agent, which is not reset even after the TM terminates and thus
accessible in the next agent step. On the other hand, at the beginning of
every agent step, the 2-4th tapes are initialized with the information of
$b(v_{\mathrm{cur}})$, the degree $\Delta(v_{\mathrm{cur}})$, and
$\pi_{\mathrm{in}}$ respectively. The 2-4th tapes are read-only in executions
of $M(A)$. The fifth tape is write-only, which initially stores only symbol
$\sqcup$ and finally stores the port number from which the agent leaves
$v_{\mathrm{cur}}$ at the termination of $M(A)$. Due to some technical reason,
we assume that the information stored in the 3-5th tapes are unary encoded,
i.e., a numerical value $k$ is encoded by $k$ iterations of 1. Note that this
assumption is not essential because unary and binary encodings are mutually
transformable in polynomial TM steps. The agent performs the local computation
following the transition function $\gamma$ until $M(A)$ terminates at state
$q_{1}$. The algorithm $A$ terminates when the local computation finishes with
writing nothing in the fifth tape (i.e., storing only $\sqcup$). The maximum
lengths $g(n)$ and $h(n)$ of the first and second tapes used by $M(A)$ over
all possible executions for graphs of at most $n$ nodes are respectively
called the _memory complexity_ and _storage complexity_ of $A$. We call $A$ a
_polynomial-time_ algorithm if for any input graph $G$ of $n$ nodes, $A$
necessarily terminates within $\mathrm{Poly}(n)$ agent steps and local
computation by $M(A)$ necessarily terminates within $\mathrm{Poly}(n)$ TM
steps.

###  2.3 Decision Task and Complexity Class

Let $\mathcal{G}$ be the set of all possible input graphs. A _decision task_
$\mathcal{T}$ is defined as a subset of $\mathcal{G}$ consisting of all “yes”
instances of that task. Assume that the storage at each node contains a
boolean output register. An algorithm $A$ solves a decision task $\mathcal{T}$
if for any input graph $G\in\mathcal{G}$ and any initial location of the
agent, the agent terminates with writing the value of the predicate
$G\in\mathcal{T}$ in the output register at the final location. We define
$\mathsf{P_{AGT}}(g(n),h(n))$ be the class of the decision tasks solvable by a
polynomial-time algorithm of memory complexity $g(n)$ and storage complexity
$h(n)$.

##  3 Lex-DFS Algorithm Using $O(1)$-bit memory and $O(1)$-bit storage

###  3.1 Lexicographically-Ordered DFS

The lexicographically-ordered depth-first search (Lex-DFS) is a special case
of the standard depth-first search, which requires some specific search order
following the port numbers: When the agent chooses an unvisited neighbor in
$N(v_{\mathrm{cur}})$, it must choose the node $u\in N(v_{\mathrm{cur}})$
whose port number $\pi_{v_{\mathrm{cur}}}(u)$ is the minimum of all unvisited
neighbors. Throughout this paper, we fix the root of the Lex-DFS search by the
initial location of the agent, which is denoted by $r$. We also define
$r=v_{0},v_{1},\dots,v_{n-1}$ as the sequence of all vertices in the input
graph $G$ following the pre-order of Lex-DFS. Fixing the root $r$, the Lex-DFS
ordering and the corresponding DFS tree is uniquely determined. We denote by
$P(v)$ the path from $r$ to $v$ in the Lex-DFS tree.

###  3.2 Procedure FindFirst

For ease of presentation, we introduce a fundamental subroutine called
FindFirst. In the design of our algorithm, the agent often has to discover the
neighbor with a specific state. The procedure FindFirst$(O,P)$ invoked at a
node $u$ visits all the neighbors $N(u)$ in the order specified by $O$ for
probing. When the agent finds the neighbor $v\in N(u)$ satisfying the
predicate $P$ on the storage contents for the first time, it goes back to $u$
and terminates. Then $\pi_{\mathrm{in}}$ indicates the port number of $v$,
i.e., it terminates with $\pi_{\mathrm{in}}=\pi_{u}(v)$. To simplify the
description of the algorithm , if there are no neighbor $v$ satisfying
$P(v)=\mathrm{True}$, FindFirst$(O,P)$ terminates with $\pi_{\mathrm{in}}=-1$
555Since the system does not have port number $-1$, it is actually implemented
by preparing one-bit flag indicating the success or failure of the exploration
in the agent state.. We can choose the search order $O$ from the following
four options: HeadAscend, MiddleAscend, MiddleDescend, TailDescend. The choice
of Head, Middle, and Tail determines the port number where the procedure
starts the search, which respectively means $0$, $\pi_{\mathrm{in}}$,
$\Delta(u)-1$. The choice of Ascend/Descend is the order of the search, each
of which corresponds to the ascending and descending orders of port numbers.
The search with option Middle is not cyclic, i.e., it terminates when the
neighbor with port number $0$ or $\Delta(u)-1$ has been probed. Note that
iterative probing of neighbors does not need any persistent counter: In the
invocation at node $v$, the agent repeats the go-and-back for each neighbor in
$N(v)$, which is implemented by the mechanism that the agent coming back to
$v$ moves to the neighbor through port $\pi_{\mathrm{in}}+1$ or
$\pi_{\mathrm{in}}-1$ according to the choice of Ascend/Descend.

###  3.3 Lex-DFS Algorithm Using $O(1)$-Bit Memory and $O(1)$-Bit Storage

This section provides the details of our small-space Lex-DFS algorithm, called
DLDFS. In the following argument, we use notation $b(v).\mathsf{q}$ to
represent the variable $\mathsf{q}$ stored in the storage $b(v)$. The
fundamental structure of DLDFS follows the centralized Lex-DFS algorithm using
only $O(n)$-bit memory space (more precisely, it manages vertex labels of
$O(1)$ bits) proposed concurrently by Asano et al. [1] and Elmasry et al. [6].
Initially, all vertices are colored by white (implying ”not visited yet”). All
visited nodes are colored by black (implying “already visited”) or grey
(implying “already visited, and on the path $P(u)$ for the location $u$ of the
DFS search head”). We refer to $P(u)$ as the _grey path_. In DLDFS, the color
of each node is managed by the storage variable $\mathsf{color}$. In the
forwarding phase, DLDFS behaves completely same as the naive Lex-DFS
algorithm. First, it checks if there exists a white neighbor of
$v_{\mathrm{cur}}$ or not. If it exists, the algorithm chooses the one with
the minimum port number as the next node, and colors the next node by grey.
This process is easily implemented by the procedure FindFirst. When no white
neighbor exists, the algorithm performs the backtrack to the parent node in
the grey path, as well as coloring the current node by black. Since storing
the pointers to the parent node at each node on $P(u)$ incurs $O(\log n)$-bit
storage cost, the technical challenge of $O(1)$-bit storage Lex-DFS lies at
how to perform backtracks without those pointers. The solution by Asano et al.
and Elmasry et al. is to resolve this mater by the following lemma, which
states that the grey path from $r$ is recovered only from the information of
the _set_ of grey nodes.

######  Lemma 1 (Asano et al. [1], Elmasry et al. [6])

Let $G=(V,E,\Pi)$ and $r\in V$ be any instance of Lex-DFS, and
$P(u)=u_{0},u_{1},\cdots,u_{k}$ ($r=u_{0}$ and $u=u_{k}$). Then, for any
$i\in[0,k-1]$, $\pi_{u_{i}}(u_{i+1})=\min\\{\pi_{u_{i}}(u_{j})\mid
j\in[i+1,k],u_{j}\in N(u_{i})\\}$ holds.

The lemma above deduces the following backtrack process at node $u$: First, we
color $u$ by an extra color (we use green for this purpose). Then the agent
starts the traversal of $P(u)$ from the root node $r$. Consider the situation
where $u_{0},u_{1},\cdots,u_{i}$ are already traversed and the algorithm at
the current node $u_{i}$ is finding the next node $u_{i+1}$. Assume that each
node maintains the boolean flag $\mathsf{traversal}$ in its storage, and all
traversed nodes set $\mathrm{True}$ to that flag. Then the algorithm can
identify $u_{i+1}$ because it is the non-flagged grey neighbor of $u_{i}$
having the minimum port number, by Lemma 1. This search task is implemented by
FindFirst. When $u_{i+1}$ is found, $\pi_{\mathrm{in}}$ indicates the port to
$u_{i+1}$. The agent visits $u_{i+1}$ and sets
$b(u_{i+1}).\mathsf{traversal}=\mathrm{True}$. Iterating this process the
algorithm completely traverses the sequence $P(u)$ and can identify the parent
of $u$ (when FindFirst finds a green neighbor, the current node is the
parent). After traversing $P(u)$, all flags must be reset, which is done by
executing the traversal from $r$ again by inverting the roles of
$\mathsf{traversal}$ (i.e., $\mathsf{traversal}=\mathrm{True}$ represents that
it is not flagged). Finally, the backtrack finishes with coloring $u$ by
black.

The remaining issue is how the agent goes back to the root $r$ to start the
traversal of $P(u)$. To address it, we introduce a new distributed date
structure called _R-path_. An instance $X$ of R-path maintains a path
connecting an arbitrary _source node_ $s$ to a _target node_ $t$. Note that
R-path structure does not store any specific path from $s$ to $t$, but some
path connecting from $s$ to $t$ admitting the traversal by the agent. In that
sense, what the R-path structure provides is only the functionality of jumping
between $s$ and $t$. The important features of R-path are twofold: We can
dynamically update the location of the target node $t$, and $O(1)$-bit memory
and storage suffice to implement it. Each instance $X$ of the R-path structure
provides the following three operations to the upper application layer. Note
that every operation can be executed only when the agent is on the managed
path, and Modify&Move can be executed only when the agent is on the target
node $t$.

  * •

MoveSource: The agent on the path managed by $X$ goes back to the source node
of $X$.

  * •

Modify&Move: The agent changes the target node of $X$ to
$\pi^{-1}_{v_{\mathrm{cur}}}(\pi_{\mathrm{in}})$, and moves there.

  * •

MoveOneHopForward: When the agent is on the path managed by $X$, it moves to
the neighbor in that path closer to the target node .

Apparently, the R-path structure is the last piece of completing DLDFS. In
running the Lex-DFS algorithm explained above, the agent manages the path from
the root $r$ to the tail of the current grey path using the R-path structure.
When it must go back to $r$ in the process of backtracks, it suffices to run
MoveSource. Assuming the R-path structure is realizable, we obtain the
following theorem.

###### Theorem 3

There exists a polynomial-time Lex-DFS algorithm using $O(1)$-bit memory and
$O(1)$-bit storage.

In the following applications, we often run DLDFS multiple times. Then all
nodes are colored by black after the first invocation of the algorithm. To run
DLDFS again, those colors must be reset to white. This matter is easily
resolved in the same way as resetting all flags in the grey path traversal.
That is, it suffices to run DLDFS again by swapping the meanings of black and
white nodes.

###  3.4 Implementation of R-path Structure

We first explain the structure of memory and storage: The agent is oblivious
in procedures MoveSource and MoveOneHopForward. The implementation of
Modify&Move uses two agent states, called _Find_ and _Delete_. The storage
consists of four variables target, inPath, direction, and color. Note that the
variable color in this section is independent of the variable with the same
name in the main Lex-DFS algorithm. The variable target is a flag indicating
the current target node. The variables inPath and direction are also the
binary flags for recording the information on the maintained path (the details
are explained later). The variable color is a mark internally used in the
procedures, which takes one of four colors
$\\{\mathrm{white},\mathrm{red},\mathrm{blue},\mathrm{yellow}\\}$. Initially,
all nodes have color $\mathrm{white}$. We call the node satisfying inPath
$=\mathrm{True}$ an _in-path node_ , and denote by $P$ the set of all in-path
nodes. The main idea for saving space is that R-path maintains the set of in-
path nodes constituting a “minimal” path from the source node to the target
node, where the minimality means that any subgraph induced by $P$ forms a path
graph. This feature guarantees that any node in $P$ has at most two neighbors
in $P$. We call the neighbors of $v$ in $P$ closer to $s$ and $t$ the
_backward_ and _forward_ neighbors of $v$ respectively, which are denoted by
$\mathrm{back}(v)$ and $\mathrm{fwd}(v)$. To traverse the maintained path
correctly, we further add one-bit information by variable direction.
Precisely, the value $\mathrm{``Backward}>\mathrm{Forward^{\prime\prime}}$
(resp. $\mathrm{``Backward}<\mathrm{Forward^{\prime\prime}}$) of variable
direction implies that the port number of the backward neighbor is greater
(resp. smaller) than that of the forward one. Supported by this information,
the agent can perform the backward and forward movement in the path correctly
utilizing the procedure FindFirst. For example, if
$\b{(}v_{\mathrm{cur}}).\textsf{direction}=\mathrm{``Backward}<\mathrm{Forward^{\prime\prime}}$
and the agent wants to find $\mathrm{back}(v_{\mathrm{cur}})$, the agent runs
FindFirst with predicate $b(\cdot).\textsf{inPath}=\mathrm{True}$ and
HeadAscend order. Then FindFirst returns the port number of
$\mathrm{back}(v_{\mathrm{cur}})$. All other cases can be processed similarly
(see Figure 1). It is straightforward to implement the procedures MoveSource
and MoveOneHopForward utilizing this mechanism.

Figure 1: Finding $\mathrm{back}(v)$ or $\mathrm{fwd}(v)$

The main technical challenge of realizing R-path is how to implement
Modify&Move. Consider the situation where the agent is on the target node $t$
and wants to update the target node with a neighbor $t^{\prime}\in N(t)$.
First, the agent colors $t^{\prime}$ with $\mathrm{yellow}$. If $t^{\prime}$
is on the maintained $s$-$t$ path, the edge $(t^{\prime},t)$ is the tail edge
of that path (Figure 2(a)). Then the update completes by simply removing it,
i.e., setting $b(t).\textsf{inPath}=\mathrm{False}$,
$b(t).\textsf{target}=\mathrm{False}$,
$b(t^{\prime}).\textsf{color}=\mathrm{white}$, and
$b(t^{\prime}).\textsf{target}=\mathrm{True}$. The case that $t^{\prime}$ is
not on the maintained $s$-$t$ path is more complicated because the resultant
$s$-$t^{\prime}$ path might not be minimal. Then, the agent moves to the
source node $s$ by invoking MoveSource, and starts the _find phase_ by
changing its state to Find. In the find phase, the agent descends the current
$s$-$t$ path by using MoveOneHopForward (Figure 2(b1)). During the phase it
also checks if the current in-path node has $t^{\prime}$ as its neighbor,
which is done by searching the yellow neighbor with FindFirst. Since the agent
keeps moving forward until $t^{\prime}$ is found in the current neighbors and
$t^{\prime}$ is found at latest, the find phase always terminates with
successfully finding the yellow neighbor. If the yellow neighbor is found at a
node $u$ (referred to as the _branching node_) for the first time, the
concatenation of the path from $s$ to $u$ and the edge $(u,t^{\prime})$
creates a new path connecting $s$ and $t^{\prime}$, which satisfies the
minimality requirement of R-path. After finding the branching node $u$, the
agent must continue to descend the $s$-$t$ path to $t$ for deleting the
expired path from $u$ to $t$. To obtain the forward way to $t$ at node $u$, we
do not immediately modify the variable direction of $u$. Instead, when $u$ is
found, the agent colors node $u$ by $\mathrm{red}$ or $\mathrm{blue}$. The
color $\mathrm{red}$ (resp. $\mathrm{blue}$) implies that the variable
direction at node $u$ must be updated by the value
$\mathrm{``Backward}>\mathrm{Forward^{\prime\prime}}$ (resp.
$\mathrm{``Backward}<\mathrm{Forward^{\prime\prime}}$). The color assigned to
$u$ can be computed by comparing the port numbers of the yellow neighbor and
$\mathrm{back}(u)$ using FindFirst, but it is not an obvious task because one
cannot distinguish $\mathrm{back}(u)$ and $\mathrm{fwd}(u)$ during the run of
FindFirst. We resolve this matter by the following strategy: The agent first
finds the port number of the yellow neighbor by FindFirst with option
HeadAscend, and then starts FindFirst again with Middle- option from the
position of the yellow neighbor to find any in-path neighbor. The search order
of the second invocation follows the ascending order if
$b(u).\textsf{direction}=\mathrm{``Backward}>\mathrm{Forward^{\prime\prime}}$
holds, or the descending order otherwise. The agent decides the color of $u$
by blue if one of the following cases applies: (1) In the ascending order
search, no in-path neighbor is found, or (2) in the descending order search an
in-path neighbor is found. The node $u$ is colored by red in all other cases.
We can see that the procedure correctly decides the color of $u$ from Figure 3
that describes all the possible cases. The actual updates of
$b(u).\textsf{direction}$ is deferred to the end of the following _delete
phase_. In the delete phase, the agent continues to descend the path with
resetting inPath by $\mathrm{False}$(Figure 2(b2)). Arriving at $t$, the agent
finds the yellow neighbor $t^{\prime}$ and moves to there. The agent sets
$b(t^{\prime}).\textsf{color}=\mathrm{white}$ and
$b(t^{\prime}).\textsf{inPath}=\mathrm{True}$, and then further moves to the
neighbor with colored by red or blue (i.e., $u$). The variable
$b(u).\textsf{direction}$ is appropriately updated according to its color.
Finally, the agent goes back to $t^{\prime}$ and the procedure finishes
(Figure 2(b3)). The pseudocode of the procedure Modify&Move and the
correctness of the R-path structure is given in the appendix.

Figure 2: The implementation of Modify&Move Figure 3: Coloring of branching
nodes. Recall that the goal of this task is to color $u$ by red if the port
number of the yellow neighbor precedes that of the backward in-path neighbor,
or by blue otherwise.

##  4 Simulation of $O(n)$-bit Agent by One-bit Agent

###  4.1 Extending R-path structure

We first introduce four additional operations for the R-path structure.

  * •

MoveTarget: The agent goes down to the target node maintained by the instance.

  * •

$\mathsf{Delete}$: Change the current target node to the current source node.

  * •

$\mathsf{Copy}$($X_{1},X_{2}$): Given two instances $X_{1}$ and $X_{2}$ of the
R-path, the path maintained by $X_{1}$ is copied to the instance $X_{2}$. That
is, by this operation, $X_{1}$ and $X_{2}$ maintains the same path. The
operation terminates at the target node of $X_{1}$ (which is equal to that of
$X_{2}$).

  * •

ModifySuccessor/ ModifyPredecessor: Change the current target node of the
instance to its successor/predecessor in the lex-DFS ordering.

The procedure MoveTarget is easily implemented by iterative invocations of
MoveOneHopForward. The procedure $\mathsf{Delete}$ is also easily implemented
by the following operations: The agent executes MoveTarget first, and then
iteratively invokes Modify&Move to change the target to its backward neighbor
until the target becomes $r$. The backward neighbor is easily found by by
running FindFirst.

The procedure $\mathsf{Copy}(X_{1},X_{2})$ first invokes $\mathsf{Delete}$ for
$X_{2}$, and then iteratively invokes Modify&Move for $X_{2}$ to move the
target of $X_{2}$ along the path maintained by $X_{1}$. That is, assuming the
target node $t$ of $X_{2}$ is on the path maintained by $X_{1}$, the procedure
finds the forward neighbor $v$ of $t$ in the path managed by $X_{1}$ using
FindFirst, and changes the target node of $X_{2}$ to $v$ by Modify&Move. When
the target node of $X_{2}$ reaches the target node of $X_{1}$, the copy from
$X_{1}$ to $X_{2}$ completes.

The implementation of ModifySuccessor and ModifyPredecessor requires a
slightly non-trivial idea. It is realized by some modified version of DLDFS
which manages an extra R-path instance $X^{\prime}$. Let $I_{j}$ be the time-
step interval in the execution of DLDFS from the first visit of $v_{j}$ to
that of $v_{j+1}$. During the period $I_{j}$, $X^{\prime}$ manages the path
connecting $r$ and $v_{j}$. Consider the invocation of ModifyPredecessor for
$X^{\prime\prime}$ with the current target node $v$. It runs MoveSource for
$X^{\prime\prime}$ to go back to the root $r$, and then starts DLDFS. At the
beginning of each $I_{j+1}$, the agent checks if $v_{j+1}=v$ holds or not. If
it holds, the target node of $X^{\prime}$ is $v_{j}$. Hence it suffices to
invoke $\mathsf{Copy}(X^{\prime},X^{\prime\prime})$ to change the target node
of $X^{\prime\prime}$ to the predecessor of $v=v_{j+1}$. Then the agent
updates $X^{\prime}$, which is done by copying the R-path instance $X$ managed
inside of DLDFS, which has the target node $v_{\mathrm{cur}}=v_{j+1}$, to
$X^{\prime}$. Finishing the run of DLDFS, the procedure terminates with the
invocation of $\mathsf{Delete}$ of $X^{\prime}$. The procedure ModifySuccessor
is implemented similarly.

###  4.2 From $O(n)$ bits to $O(1)$ bits

For simplicity, we construct the simulation algorithm $\mathit{Sim}(A)$ for
any algorithm $A$ using $n$-bit memory and $O(1)$-bit storage, but it is easy
to extend $\mathit{Sim}(A)$ for supporting general $O(n)$-bit memory. As
stated in the introduction, the key idea of the simulation is the distributed
management of the tapes of $M(A)$ using the serialization of all nodes by
DLDFS. To refer to the status of the simulated algorithm $A$, we use the
notations with upper script $A$, e.g., $v_{\mathrm{cur}}^{A}$ denotes the
current location of the simulated agent running $A$. The storage $b^{A}(v)$ of
node $v$ in $A$ is also stored at $v$ in $\mathit{Sim}(A)$. The $i$-th node
$v_{i}$ in the lex-DFS ordering stores the $i$-th bit of each tape. Hence we
treat the vertices $v_{0},v_{1},\dots,v_{n-1}$ as the address of each tape,
i.e., we say “the $j$-th tape head is at $v_{i}$” to imply the $j$-th tape
head is at the $i$-th entry of the tape. The location of the $j$-th tape head
of $M$ is denoted by $t_{j}$ ($1\leq j\leq 5$). To keep the information of
those locations, the algorithm $\mathit{Sim}(A)$ manages six independent
instances of the R-path, each of which is denoted by $X(z)$ for
$z\in\\{v_{\mathrm{cur}}^{A},t_{1},t_{2},t_{3},t_{4},t_{5}\\}$ and manages a
path from $v_{0}$ to $z$. In addition, each node has one-bit flag
$\mathit{past}$ in its storage, which becomes $\mathrm{True}$ if and only if
the node is the location of the simulated agent one-step before. The state of
$M(A)$ is stored in the memory of the simulator agent running
$\mathit{Sim}(A)$. Obviously, the structure explained above incurs only
$O(1)$-bit memory and $O(1)$-bit storage per node. The one-step execution of
$A$ performed at $v_{\mathrm{cur}}^{A}$ is simulated by the following phases.

  * •

Initialization phase : As defined in Section 2, the 2-4th tapes must be
initialized by the information of $b^{A}(v_{\mathrm{cur}}^{A})$, the degree of
$v_{\mathrm{cur}}^{A}$, and $\pi_{\mathrm{in}}^{A}$. Copying the information
$b^{A}(v_{\mathrm{cur}}^{A})$ into the second tape is straightforward: The
simulator agent stores whole information of $b^{A}(v_{\mathrm{cur}}^{A})$ in
its memory and takes it to the second tape by invoking MoveSource for
$X(v_{\mathrm{cur}}^{A})$ and MoveTarget for $X(t_{2})$. The initialization of
the third and fourth tapes are slightly different because the information to
be copied is not explicitly stored in $v_{\mathrm{cur}}^{A}$. Recall that the
information in these two tapes is unary encoded. To read the information, we
use a similar technique as FindFirst, where the agent probes all neighbors of
$v_{\mathrm{cur}}^{A}$ in the ascending order of their port numbers with
tracking $v_{\mathrm{cur}}$ by an extra R-path instance $X(v_{\mathrm{cur}})$.
Consider an example of copying the information of the degree of
$v_{\mathrm{cur}}^{A}$ to the third tape. The agent appends 1 at the next
position of $t_{3}$ when it visits one neighbor of $v_{\mathrm{cur}}^{A}$, by
traversing the paths managed by $X(v_{\mathrm{cur}})$ and $X(t_{2})$. After
probing all neighbors, the third tape obviously stores the unary encoding of
the degree information. The initialization of $t_{4}$ is also handled
similarly (the details are deferred to the appendix).

  * •

Local simulation phase : The simulator agent iteratively simulates one TM step
of $M$ until $M$ terminates. The agent first collects the values of the
entries pointed by the tape heads. It is easily processed by the procedures
MoveSource and MoveTarget. The simulation of one TM step is the local
computation of the agent. After the computation, the agent must update the
tape contents, and move the tape heads. It is also easily implemented by
ModifySuccessor and ModifyPredecessor.

  * •

Agent movement phase: When $M$ terminates, the first tape stores the state of
the simulated agent after the local computation, and the fifth tape stores the
port number to which the simulated agent goes out from $v_{\mathrm{cur}}^{A}$.
Updating $v_{\mathrm{cur}}^{A}$ is seen as the “inverse” operation of
initializing the fourth tape. Hence one can implement it in a similar way as
the initialization phase (the details are deferred to the appendix).

###  4.3 From $O(1)$ bits to One bit

Let $A$ be any algorithm for the system with $O(1)$-bit memory and $O(1)$-bit
storage. We simulate this algorithm by the one-bit memory agent. Let us denote
by $\mathit{Sim}(A)$ the simulator algorithm, and $\mathsf{a}$ be the memory
of the simulator agent. In $\mathit{Sim}(A)$, the storage of each node $v$
consists of two variables $\mathsf{st}$ and $\mathsf{mem}$, and an auxiliary
integer variable $\mathsf{trans}$. Intuitively, $\mathsf{st}$ works as the
storage of the simulated algorithm $A$, and $\mathsf{mem}$ is used as the
memory of the simulated algorithm. The contents of $\mathsf{st}$ and
$\mathsf{mem}$ are represented by fixed-length binary sequences. Let $c$ be
the length of $\mathsf{mem}$. Our simulation algorithm satisfies the following
invariants at the beginning of the one-step simulation: (1) For any $v\in V$,
$b(v).\mathsf{trans}=0$ and $b(v).\mathsf{st}=b^{A}(v)$, (2)
$b(v_{\mathrm{cur}}^{A}).\mathsf{mem}=\mathsf{a}^{A}$, and (3)
$\pi_{\mathrm{in}}=\pi_{\mathrm{in}}^{A}$ and
$v_{\mathrm{cur}}=v_{\mathrm{cur}}^{A}$.

We refer to the node $v_{\mathrm{cur}}^{A}$ as the _departure node_ and refer
to the neighbor of $v_{\mathrm{cur}}^{A}$ the simulated agent visits next as
the _destination node_. Since the simulator agent has only one-bit memory, it
cannot take any additional control information. The $j$-th entry of
$\mathsf{mem}$ is referred to as $\mathsf{mem}[j]$ ($0\leq j\leq c-1$). Hence
the agent needs to know the current context only from the information of the
storage at the departure node and the destination node. The detailed
description of the simulator agent at a node $u$ is given as follows:

  * •

If $b(u).\mathsf{trans}>0$ when the agent visits $u$ but $b(u).\mathsf{trans}$
is reset to zero in the local computation (where the local computation up to
the reset belongs to the past one-step simulation), the simulator agent starts
the simulation of $A$ regarding $u$ as the departure node. Using the space
$b(u).\mathsf{mem}$ as the first tape of $M(A)$ and $b(u).\mathsf{st}$ as the
second tape of $M(A)$, it simulates the run of $M(A)$. The information of
$\pi_{\mathrm{in}}^{A}$ is available due to the third invariant above. When
$M(A)$ terminates, the fifth tape correctly stores the destination node. Then
the simulator agent fetches $b(u).\mathsf{mem}[b(u).\mathsf{trans}]$ to
$\mathsf{a}$, decrements $b(u).\mathsf{trans}$, and moves to the computed
destination node.

  * •

If $0\leq b(u).\mathsf{trans}(u)<c-1$ holds when the simulator agent visits
$u$, the current situation is recognized as in transferring the information of
$\mathsf{mem}$ and at the destination node. Hence the simulator agent sets
$b(u).\mathsf{mem}[b(u).\mathsf{trans}]=\mathsf{a}$, increments
$b(u).\mathsf{trans}$, and goes back to $\pi_{\mathrm{in}}$.

  * •

If $-(c-1)<b(u).\mathsf{trans}(u)<0$ holds when the simulator agent visits
$u$, the current situation is recognized as in transferring the information of
$\mathsf{mem}$ and at the departure node. Hence the simulator agent fetches
$b(u).\mathsf{mem}[-(b(u).\mathsf{trans})]$ to $\mathsf{a}$, decrements
$b(u).\mathsf{trans}$, and goes back to $\pi_{\mathrm{in}}$.

  * •

If $b(u).\mathsf{trans}(u)=-(c-1)$ holds when the simulator agent visits $u$,
the simulator agent finds that transferring $\mathsf{mem}$ finishes and the
current location is the departure node. Hence it resets $b(u).\mathsf{trans}$
to zero and moves to $\pi_{\mathrm{in}}$.

  * •

If $\mathsf{trans}(u)=c-1$ holds when the simulator agent visits $u$, the
simulator agent finds that transferring $\mathsf{mem}$ finishes and the
current location is the destination node. Hence by resetting
$b(u).\mathsf{trans}$ to zero, the current one-step simulation finishes and
then proceeds to the next one-step simulation.

It is easy to check that all the invariants are satisfied at the end of the
one-step simulation. Also, the correctness of the simulation is easily deduced
from the invariants. Combining the simulation algorithms of Section 4.2 and
4.3, we obtain Theorem 1.

## Acknowledgement

The authors would like to thank Shantanu Das for his suggestion on the
simulation by one-bit agent.

## References

  * AIK+ [14] Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara.  Depth-first search using $\mathcal{O}(n)$ bits.  In Proc. of 25th International Symposium on Algorithms and Computation (ISAAC), pages 553–564, 2014.
  * AKL+ [79] Romas Aleliunas, Richard M. Karp, Richard J. Lipton, Laszlo Lovasz, and Charles Rackoff.  Random walks, universal traversal sequences, and the complexity of maze problems.  In Proc. of SFCS ’79 Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FORCES), pages 218–223, 1979.
  * BGH+ [09] Evangelos Bampas, Leszek Ga̧sieniec, Nicolas Hanusse, David Ilcinkas, Ralf Klasing, and Adrian Kosowski.  Euler tour lock-in problem in the rotor-router model.  In Proc. of 23rd International Symposium on Distributed Computing (DISC 2009), pages 423–435, 2009.
  * CFI+ [08] Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, and David Peleg.  Label-guided graph exploration by a finite automaton.  ACM Trans. Algorithms, 4(4), 2008.
  * DHK [16] Yann Disser, Jan Hackfeld, and Max Klimm.  Undirected graph exploration with $\theta$ (log log n) pebbles.  In Proc. of 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 25–39, 2016.
  * EHK [15] Amr Elmasry, Torben Hagerup, and Frank Kammer.  Space-efficient Basic Graph Algorithms.  In Proc. of 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30, pages 288–301, 2015.
  * [7] Uriel Feige.  A spectrum of time-space trade-offs for undirected $s$-$t$ connectivity.  Journal of Computer and System Sciences, 54:305–316.
  * FIP+ [05] Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, and David Peleg.  Graph exploration by a finite automaton.  Theoretical Computer Science, 345:331–344, 2005.
  * HW [93] Shlomo Hoory and Avi Wigderson.  Universal traversal sequences for expander graphs.  Information Processing Letters, 46:67–69, 1993.
  * Ist [88] Sorin Istrail.  Polynomial universal traversing sequences for cycles are constructible.  In Proc. of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), pages 491–503, 1988.
  * Kos [13] Adrian Kosowski.  Faster walks in graphs: a $\tilde{O}(n^{2})$ time-space trade-off for undirected $s$-$t$ connectivity.  In Proc. of the Twenty-fourth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1873–1883, 2013.
  * Kou [02] Michal Koucký.  Universal traversal sequences with backtracking.  Journal of Computer and System Sciences, 65:717–726, 2002.
  * Kou [03] Michal Koucky.  Log-space constructible universal traversal sequences for cycles of length $\mathcal{O}(n^{4.03})$.  Theoretical Computer Science, 296:117–144, 2003.
  * [14] Howard J. Karloff, Ramamohan Paturi, and Janos Simon.  Universal traversal sequence of length $n^{O(logn)}$ for cliques.  Information Proceeding Letters, 28:241–243.
  * Rei [08] Omer Reingold.  Undirected connectivity in log-space.  Journal of the ACM (JACM), 55:17, 2008.
  * SBN+ [15] Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa.  A single agent exploration in unknown undirected graphs with whiteboards.  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E98.A(10):2117–2128, 2015.
  * Sha [51] Claude E. Shannon.  Presentation of a maze-solving machine.  8th Conference of the Josiah Macy Jr. Foundation (Cybernetics), pages 173–180, 1951.

##  5 Correctness of the R-Path Structure

###  5.1 Pseudocode of Modify&Move

To present the algorithm of Modify&Move, we introduce an auxiliary procedure
called MarkPred$(I)$. It updates the whiteboard
$b(\pi^{-1}_{v_{\mathrm{cur}}}(\pi_{\mathrm{in}}))$ following the instruction
$I$. The actual behavior inside the procedure is that the agent first goes to
$\pi^{-1}_{v_{\mathrm{cur}}}(\pi_{\mathrm{in}})$, updates the contents of
$b(\pi^{-1}_{v_{\mathrm{cur}}}(\pi_{\mathrm{in}}))$ following $I$, and goes
back to $v_{\mathrm{cur}}$. Note that the value of $\pi_{\mathrm{in}}$ and
$v_{\mathit{cur}}$ does not change before and after the run of the procedure.
The pseudocode of the procedure Modify&Move is presented in Algorithm 1.

Algorithm 1 Modify&Move($x$)

1:MarkPred(color$\leftarrow$ yellow) $\triangleright$ Color the new target
node.

2:$\pi_{\mathrm{in}}\leftarrow$ FindFirst(HeadAscend, inPath $=$
$\mathrm{True}$$\land$ color $=$ $\mathrm{yellow}$)

3:if $\pi_{\mathrm{in}}\neq-1$ then $\triangleright$ Find the yellow node on
the path.

4: $b(v_{\mathrm{cur}})$.($\mathsf{target}$, $\mathsf{inPath}$) $\leftarrow$
($\mathrm{False}$, $\mathrm{False}$)

5: MarkPred(target $\leftarrow$ $\mathrm{True}$; color $\leftarrow$
$\mathrm{white}$)

6: Move to $\pi_{\mathrm{in}}$ and Halt

7:else

8: $q\leftarrow$ Find; MoveSource()

9:while True do

10: if $q=$ Find then

11: $\pi_{\mathrm{in}}\leftarrow$FindFirst(HeadAscend, color $=$
$\mathrm{yellow}$)

12: if $\pi_{\mathrm{in}}\neq-1$ then $\triangleright$ Finds the
yellow(target) node from the neighbors.

13: $q\leftarrow$ Delete

14: $b(v_{\mathrm{cur}})$.color $\leftarrow$ $\mathrm{red}$ $\triangleright$
$v_{\mathrm{cur}}$ is the predecessor of the new target on R-path.

15: if $b(v_{\mathrm{cur}})$.direction $=$
$\mathrm{``Backward}>\mathrm{Forward^{\prime\prime}}$ then

16: $\pi_{\mathrm{in}}\leftarrow$FindFirst(MiddleAscend, inPath $=$
$\mathrm{True}$)

17: if $\pi_{\mathrm{in}}=-1$ then $\triangleright$ backward $<$ new target

18: $b(v_{\mathrm{cur}})$.color $\leftarrow$ $\mathrm{blue}$

19: else

20: $\pi_{\mathrm{in}}\leftarrow$FindFirst(MiddleDescend, inPath $=$
$\mathrm{True}$)

21: if $\pi_{\mathrm{in}}\neq-1$ then $\triangleright$ backward $<$ (forward
$<$) new target

22: $b(v_{\mathrm{cur}})$.color $\leftarrow$ $\mathrm{blue}$

23: MoveOneHopForward()

24: if $q=$ Delete then

25: if $b(v_{\mathrm{cur}})$.target $=$ $\mathrm{True}$ then

26: $b(v_{\mathrm{cur}})$.($\mathsf{target}$, $\mathsf{inPath}$) $\leftarrow$
($\mathrm{False}$, $\mathrm{False}$) $\triangleright$ Removing the old target

27: $\pi_{\mathrm{in}}\leftarrow$ FindFirst(HeadAscend, color $=$ yellow)

28: Move to $\pi_{\mathrm{in}}$ $\triangleright$ Move to the new target node.

29: $b(v_{\mathrm{cur}})$.($\mathsf{color}$, $\mathsf{inPath}$,
$\mathsf{target}$) $\leftarrow$ ($\mathrm{white}$, $\mathrm{True}$,
$\mathrm{True}$) $\triangleright$ Set up the new target

30: $\pi_{\mathrm{in}}$$\leftarrow$ FindFirst(HeadAscend, color $=$
$\mathrm{red}$)

31: if $\pi_{\mathrm{in}}=-1$ then $\triangleright$ Branching node is blue

32: $\pi_{\mathrm{in}}\leftarrow$ FindFirst(HeadAscend, color $=$
$\mathrm{blue}$)

33: MarkPred(direction
$\leftarrow\mathrm{``Backward}<\mathrm{Forward^{\prime\prime}}$)

34: else$\triangleright$ Branching node is red

35: MarkPred(direction
$\leftarrow\mathrm{``Backward}>\mathrm{Forward^{\prime\prime}}$)

36: MarkPred(color $\leftarrow$ $\mathrm{white}$) $\triangleright$ Clean up
the predecessor in the path

37: MarkPred(inPath$\leftarrow$ $\mathrm{True}$)

38: Halt

39: else

40: MoveOneHopForward() $\triangleright$ Traversal of the expired path

41: MarkPred(inPath $\leftarrow$ $\mathrm{False}$)

###  5.2 Correctness Proof

It is obvious that the success of the operations MoveSource and
MoveOneHopForward relies on whether the procedure Modify&Move correctly
manages the contents of variables inPath and direction. We first present the
correctness criteria of the R-path.

###### Definition 1

We say that an instance $X$ of the R-path is _consistent_ with respect to the
source node $s$ and the target node $t$ if the following conditions are
satisfied.

  1. 1.

$b(t).{\textsf{target}}=\mathrm{True}$..

  2. 2.

Each connected component of the subgraph $G^{\prime}$ of $G$ induced by the
nodes satisfying $\textsf{inPath}=\mathrm{True}$ is a path graph.

  3. 3.

Let $P^{\prime}=v_{1},v_{2},\cdots,v_{h}$ be any connected component
$G^{\prime}$ such that $v_{1}=x$ or $v_{h}=y$ holds. For any $v_{i+1}(1\leq
i\leq h-1)$, if $\pi_{v_{i+1}}(v_{i})$ is grater than
$\pi_{v_{i+1}}(v_{i+2})$, then
$b(v_{i+1})=\mathrm{``Backward}>\mathrm{Forward^{\prime\prime}}$ holds, and
$b(v_{i+1})=\mathrm{``Backward}<\mathrm{Forward^{\prime\prime}}$ holds
otherwise.

In addition, if the number of connected components in $G^{\prime}$ is one, we
say that the R-path data structure is _strongly consistent_.

When an instance $X$ is consistent, we call any connected subgraph managed by
$X$ (not necessarily a connected component) a _fragment_. By definition, each
fragment is a path graph, and has backward and forward directions determined
by variable direction. A fragment with top node $x$ and bottom node $y$ is
called an $x$-$y$ fragment. From the definition, if $X$ is strongly
consistent, its (unique) connected component is the $s$-$t$ fragment. For a
node $z$ in an $x$-$y$ fragment, the backward and lower neighbors of $z$ in
the fragment are denoted by $\mathrm{back}(z)$ or $\mathrm{fwd}(z)$. The
correctness of R-path is captured by the following two lemmas:

###### Lemma 2

Assume that the R-path is consistent and $v_{\mathrm{cur}}$ is contained in a
$x$-$y$ fragment. Then after running MoveOneHopForward or MoveSource, the
agent stays at $\mathrm{fwd}(v)$ or $x$ respectively.

###### Proof.

As we discussed above, as long as the R-path is consistent, the agent
correctly finds backward or forward in-path neighbors. Thus the lemme
obviously holds. ∎

###### Lemma 3

At the invocation of MoveOneHopForward and MoveSource in any execution of
Modify&Move, the R-path is consistent (and thus those operations work
correctly). In addition, at the end of executing Modify&Move, the R-path is
strongly consistent.

###### Proof.

In Find phases, the agent does not modify inPath or direction at any node.
Thus the lemma obviously holds. In Delete phases, letting $u$ be the branching
node, the $s$-$u$ fragment is preserved during the phase, and the agent
gradually deletes the information on the prefix of the $u$-$t$ fragment. More
precisely, if the agent stays at node $u^{\prime}$ in the Delete phase,
$u^{\prime}$-$t$ fragment is preserved (and thus consistent). That is,
MoveOneHopForward performed at $u^{\prime}$ correctly works. It implies that
$u$-$t$ fragment is correctly deleted, and the agent eventually reaches
$t^{\prime}$. At $t^{\prime}$, $b(t^{\prime}).\textsf{inPath}$ becomes true,
and thus the remaining issue is to show that the subset $P^{\prime}$
consisting all the nodes in the $s$-$u$ fragment and $t^{\prime}$ satisfies
the strong consistency. It is obvious that $P^{\prime}$ induces one connected
subgraph. In addition, except for $u$, no node in $P^{\prime}$ has
$t^{\prime}$ as its neighbor. That is, $P^{\prime}$ induces a path graph. On
the information stored in variable direction, no node except for $u$ takes any
update, and thus the correctness is preserved. The variable
$b(u).\textsf{direction}$ is consistently updated in the run of Modify&Move,
which is verified by checking all the cases of Figure 3. The lemma is proved.
∎

##  6 Omitted Details of Simulation Algorithms from $O(n)$ Bits to $O(1)$ Bits

#### Initialization Phase

Only the non-trivial point deferred in the main body of the manuscript is the
details of initializing the third and fourth tapes. We focus on the
implementation of initializing the third tape, i.e., writing
$\Delta(v_{\mathrm{cur}}^{A})$ symbols of 1 to the third tape. First, the
simulator agent marks the node $v_{\mathrm{cur}}^{A}$, and then visits all the
neighbors of $v_{\mathrm{cur}}^{A}$ in the ascending order of their port
numbers as ${\textsf{FindFirst}}(\mathrm{HeadAscend},\cdot)$. During this
process, the location of the simulator agent is always tracked by the R-path
instance $X(v_{\mathrm{cur}})$. When the simulator agent visits any neighbor
$v$ of $v_{\mathrm{cur}}^{A}$, there exists a traversable path from $v$ to
$t_{3}$ managed by $X(v)$ and $X(t_{3})$ Using that path, the simulator agent
moves to $t_{3}$ and appends symbol 1 to the tail of the third tape. Then it
moves the position of $t_{3}$ by invoking ModifySuccessor for $X(t_{3})$, and
returns to $v$. To go back to $v_{\mathrm{cur}}^{A}$, the simulator agent
needs to identify the marked neighbor, which is done by FindFirst. After
repeating this process until the simulator agent visits all neighbors of
$v_{\mathrm{cur}}^{A}$, the third tape contains $\Delta(v_{\mathrm{cur}}^{A})$
symbols of 1. The initialization of the fourth tape is almost the same as that
of the third tape. Only the difference is to iterate appending symbol 1 until
the simulator agent finds the neighbor with $\mathit{past}=\mathrm{True}$,
instead of visiting all neighbors.

#### Agent Movement Phase

Let $p$ be the number of the port to which the simulated agent moves, i.e.,
the port number written in the fifth tape in the local computation phase.
Similarly to the initialization phase, the node $v_{\mathrm{cur}}^{A}$ is
marked at the beginning of the phase. We refer to the target node of
$X(v_{\mathrm{cur}}^{A})$ as $v$. To change $v$ to
$\pi_{v_{\mathrm{cur}}^{A}}(p)$, the simulator agent first places it on
$\pi_{v_{\mathrm{cur}}^{A}}(0)$. Assume that $v=\pi_{v_{\mathrm{cur}}^{A}}(j)$
for some $0\leq j\leq\Delta(v_{\mathrm{cur}}^{A})-1$. Then the simulator agent
moves to $t_{5}$ using the path managed by $X(v)$ and $X(t_{5})$, and checks
if the symbol 1 is still contained in the fifth tape or not. If the fifth tape
does not contain 1, then $j=p$ holds and thus the movement phase finishes.
Otherwise, after deleting one symbol 1 in the fifth tape, the simulator agent
goes back to $v=\pi_{v_{\mathrm{cur}}^{A}}(j)$. Then it changes the location
of $v$ to $\pi_{v_{\mathrm{cur}}^{A}}(j+1)$, which is realized by invoking
Modify&Move twice: The agent first finds the marked neighbor of $v$ (i.e.,
$v_{\mathrm{cur}}^{A}$), and moves $v$ to there by invoking Modify&Move for
$X(v)$. Since the simulator agent moves from $\pi_{v_{\mathrm{cur}}^{A}}(j)$
to $v_{\mathrm{cur}}^{A}$ at the last step of Modify&Move, $\pi_{\mathrm{in}}$
stores the value $j$ immediately after the first invocation of Modify&Move. By
going out from $v_{\mathrm{cur}}^{A}$ through the port $\pi_{\mathrm{in}}+1$
and coming back to $v_{\mathrm{cur}}^{A}$, $\pi_{\mathrm{in}}$ is updated by
$j+1$. The second invocation of Modify&Move for $X(v)$ takes $v$ to
$\pi_{v_{\mathrm{cur}}^{A}}(j+1)$. Finally, the phase finishes with unmarking
$v_{\mathrm{cur}}^{A}$ and setting
$b(v_{\mathrm{cur}}^{A}).\mathsf{past}=\mathrm{True}$.

##  7 Proof of Theorem 2

In this section, we prove Theorem 2 by showing that the following task cannot
be solved only by the agent with zero-bit memory.

######  Problem 1 (Task $\mathsf{Parity}$)

The task $\mathsf{Parity}$ consists of all the graphs with a odd number of
vertices.

It is easy to show that
$\mathsf{Parity}\in\mathsf{P_{AGT}}(O(n),\Theta(1))=\mathsf{P_{AGT}}(1,\Theta(1))$
holds: The agent counts up the modulo 2 of $n$ by running DLDFS. However, this
task cannot be solved by the zero-bit agent.

###### Lemma 4

$\mathsf{Parity}\notin\mathsf{P_{AGT}}(0,\Theta(g(1)))$.

###### Proof.

Suppose for contradiction that an algorithm $A$ solves $\mathsf{Parity}$ using
zero-bit memory and $O(1)$-bit storage. Due to the impossibility result by
Cohen et al. [4] there exists no graph exploration algorithm using zero-bit
memory and $O(1)$-bit storage. Hence there exists the graph $G=(V,E,\Pi)$ and
the initial location $v\in V$ such that $A$ decides if $G\in{\mathsf{Parity}}$
or not without vising all the nodes in $G$. Let $u\neq v$ be the node not
visited by the agent in the execution of $A$, and constructs the graph
$G^{\prime}=(V^{\prime},E^{\prime},\Pi^{\prime})$ obtained from $G$ by adding
one node $u^{\prime}$ and the edge $(u,u^{\prime})$. Since the agent does not
visit $u$, it cannot distinguish $G$ and $G^{\prime}$ and thus the decision
for those graphs are the same. However, the parity of $|V|$ and $|V^{\prime}|$
are different. It is a contradiction. ∎

This lemma obviously deduces Theorem 2.


What is given more weight in assignments: understanding course material,
application of learned principles, visual design, creative ideas, other
factors?

  * •

Do weights vary across assignments? How?

  * •

How are grading rubrics applied? Are there macro and micro level guidelines
based on the learning objectives of that assignment?

  * •

What instructions are TAs / graders given toward applying the rubric? How is
consistency ensured?

  * •

Do you use peer review for grading? Do the guidelines differ? How?

  * •

How do you understand the picture of a class? for e.g., How is a class doing
overall? What are common and specific problems?

  * •

How do you address the common and specific problems?

  * •

Do you think that the design process / addressing of problems could be better
supported by seeing students’ progress more regularly?

  * •

What do you think about our intention to design computer algorithms that
measure aspects of design work that are representative of the criteria in your
grading rubrics?

  * •

Would some kind of analytics based on the grading rubric be helpful?

  * •

Would some representations of their work be useful, e.g. conceptual themes,
assignment sections?

  * •

Would a dashboard interface help in this regard (show a mockup)?

  * •

What else could be useful?

  * •

What features would you like to see? Examples, sorting, mean, median,
outliers?

  * •

What other features do you think would be useful?

###  A.2. Workshop Discussion

For workshop, while we had put together a list of topics, the discussion
emerged on its own after instructors finished presenting their design ideation
assignments, along with assessment approach. Topics that emerged included:

  * •

the sizes of courses, teaching teams, and student teams;

  * •

the level of details in assignment and rubric specifications;

  * •

challenges in tracking students’ progress and incorporation of feedback; and

  * •

difficulty assessing contributions in team assignments.

##  Appendix B Design Characteristics Across Fields

In Section 5.2, we developed a set of situated design creativity
analytics—Fluency, Flexibility, Visual Consistency, Multiscale Organization,
and Legible Contrast—that can provide AI-based, on demand, actionable
assessment to design students. Here, we enumerate additional characteristics
identified through co-design engagements with design instructors across
fields.

Analytic |  Landscape Architecture & Urban Planning |  Computer Science and Engineering |  Mechanical Engineering |  Interactive Art & Design | Architecture
---|---|---|---|---|---
Fluency |  |  | $\bullet$ | $\bullet$ |
Flexibility |  | $\bullet$ | $\bullet$ | $\bullet$ |
Visual Consistency | $\bullet$ | $\bullet$ |  |  | $\bullet$
Multiscale Organization | $\bullet$ | $\bullet$ |  |  |
Legible Contrast | $\bullet$ | $\bullet$ |  |  |
Team Members’ Contribution | $\bullet$ | $\bullet$ | $\bullet$ | $\bullet$ |
Novelty |  | $\bullet$ | $\bullet$ |  |
Relative Object Sizes | $\bullet$ |  |  |  | $\bullet$
Number of Iterations | $\bullet$ |  | $\bullet$ |  |
Use of Small Multiples (Tufte et al., 1990) | $\bullet$ |  |  |  |
Range of Colors | $\bullet$ |  |  |  |
Coverage of Assigned Sources |  | $\bullet$ |  |  |
Edits during Practice | $\bullet$ |  |  |  |
Table 2. Learning analytics relevant to design education. In the top part, we
list analytics for which we developed AI-based approaches in the paper. In the
bottom part, we list additional characteristics that instructors in our study
emphasize. We prioritized developing analytics based on: a) the number of
contexts which emphasize a design characteristic and b) the extent of
conceptual and empirical evidence we identified in regard to developing an
effective AI approach for the corresponding analytic.