# Sparse dynamic network reconstruction through $L_{1}$-regularization of a
Lyapunov equation

Ian Xul Belausteguia Marcela Ordorica Arangoa Roman Rossi-Poolb
Naomi Ehrich Leonarda Alessio Francic a Department of Mechanical and Aerospace
Engineering, Princeton University<EMAIL_ADDRESS>Instituto de Fisiología Celular - Neurociencias and Centro de Ciencias de la
Complejidad, Universidad Nacional Autónoma de México, México;
<EMAIL_ADDRESS>Department of Electrical Engineering and Computer Science,
University of Liege, and WEL Research Institute, Wavre, Belgium;
<EMAIL_ADDRESS>
###### Abstract

An important problem in many areas of science is that of recovering
interaction networks from simultaneous time-series of many interacting
dynamical processes. A common approach is to use the elements of the
correlation matrix or its inverse as proxies of the interaction strengths, but
the reconstructed networks are necessarily undirected. Transfer entropy
methods have been proposed to reconstruct directed networks but the
reconstructed network lacks information about interaction strengths. We
propose a network reconstruction method that inherits the best of the two
approaches by reconstructing a directed weighted network from noisy data under
the assumption that the network is sparse and the dynamics are governed by a
linear (or weakly-nonlinear) stochastic dynamical system. The two steps of our
method are i) constructing an (infinite) family of candidate networks by
solving the covariance matrix Lyapunov equation for the state matrix and ii)
using $L_{1}$-regularization to select a sparse solution. We further show how
to use prior information on the (non)existence of a few directed edges to
drastically improve the quality of the reconstruction.

network identification, network inference, stochastic network dynamics, linear
programming

##  1 Introduction

In many areas of science it is common to record simultaneous time-series of
interacting dynamical processes. A natural and important problem is then to
develop data-driven methods that can recover, or reconstruct, the underlying
interaction network, possibly including information about both the direction
and the strength of the interactions. Reconstructing interaction networks has
applications, e.g., in neuroscience (between neurons or neuronal populations),
in ecology (i.e., between species populations in a community), in molecular
biology (i.e., between expression of genes), and in social sciences (i.e.,
between opinionated individuals).

An established approach, commonly employed in neuroscience applications [1, 2,
3], is to use correlation measures to approximate interaction networks through
the entries of the covariance matrix or its inverse, the precision matrix.
Networks reconstructed from the precision matrix were found to better
correlate to the underlying anatomical network [1]. However, whether using the
correlation or the precision matrix, the reconstructed network will
necessarily be undirected because both matrices are symmetric.

In order to reconstruct directed network interactions, transfer entropy (TE)
[4] has emerged as a powerful information-theoretical measure of directed
information transfer between dynamical processes, with many applications in
neuroscience [5, 6, 7, 8, 9]. However, transfer entropy methods can only
reconstruct unweighted directed interaction networks, i.e., they can only
provide information about whether a process directly affects (or not) another
but not the strength or sign of this directed interaction.

We introduce a novel method to reconstruct directed and weighted dynamical
networks under the assumption that the network dynamics can be modelled by a
linear (or weakly non-linear) stochastic differential equation driven by a
white noise vector. When used to describe resting state brain activity, this
model is known as the linear Dynamical Causal Model [10, 11]. Under this
assumption, the covariance matrix of the model is the solution to a Lyapunov
equation that links it to the state matrix of the network [12, 13]. If the
state matrix is assumed to be symmetric (i.e., the network is undirected) and
the noise components are uncorrelated, then solving the Lyapunov equation for
the state matrix returns exactly the precision matrix [1]. But if no symmetry
assumptions are made, then solving the Lyapunov equation for the state matrix
returns a whole affine subspace of candidate solutions. Under the extra
assumption that the interaction network is sparse, $L_{1}$-regularization can
effectively select a sparse solution from among the candidates. Prior
knowledge on edge existence can be included in the constraints of the
resulting linear programming (LP) problem to enhance the method performance.

The main contribution of the paper is to formulate an $L_{1}$-regularization
problem for sparse network reconstruction as an LP optimization problem over
the affine solution space of all state matrices that solve the covariance
Lyapunov equation for a given covariance matrix. Crucially, this requires the
preliminary construction of an isomorphism from such a solution space to the
solution space of an underdetermined linear system of equations. The second
contribution is to show how to introduce prior knowledge on edge existence
into the constraints of the LP problem. The third contribution is to suggest
the use of a TE-based network inference algorithm as a way of obtaining some
priors on edge existence and show that it significantly improves the quality
of network reconstruction. As an auxiliary contribution, we propose a simple
algorithm to construct sparse Hurwitz matrices.

The paper is structured as follows. Notation is introduced in Section 2. The
network model and its interpretation are introduced in Section 3. Section 4
studies the geometry of the solution space of the covariance Lyapunov equation
for the state matrix and introduces the isomorphism needed for the LP
formulation of an $L_{1}$-regularization problem over this space. Section 5
explicitly describes the LP formulation of the $L_{1}$-regularization problem.
Section 6 shows how prior information about edge existence can be incorporated
into the constraints of the LP problem. Section 7 introduces an algorithm
based on TE to provide prior knowledge on edge existence and show how to use
it to constrain the LP problem. Finally, Section 8 presents extensive
numerical validation results obtained over large families of randomly
generated sparse Hurwitz matrices. Conclusions and perspectives are presented
in Section 9.

##  2 Notation

We denote $[n]=\\{1,...,n\\}$. Given $n,m\in\mathbb{N}$, we write
$\mathbb{R}^{m\times n}$ for the set of $m$ by $n$ matrices with real entries.
For $i\in[m]$, and $j\in[n]$, the value at the $i$-th row and $j$-th column of
$A\in\mathbb{R}^{m\times n}$ is $A_{i,j}$. The column-stack vectorization
isomorphism $\text{vec}:\mathbb{R}^{m\times n}\to\mathbb{R}^{mn}$ is given by
$(\text{vec}(A))_{m(j-1)+i}=A_{i,j}$. Vector $\mathbf{1}_{n}\in\mathbb{R}^{n}$
consists of $n$ entries equal to $1$ (and similarly for $\mathbf{0}_{n}$). The
set of eigenvalues of $B\in\mathbb{R}^{n\times n}$ is $\sigma(B)$. The real
part of $z\in\mathbb{C}$ is denoted $\Re(z)$.

##  3 Model formulation

We consider a network model described by the stochastic differential equation
(SDE) [13]

$\frac{dx}{dt}(t)=Ax(t)+w(t)$ (1)

where $w$ is a white noise vector (with spectral density matrix $Q=I$) and
$A\in\mathbb{R}^{n\times n}$ is a Hurwitz matrix, i.e., all of its eigenvalues
have a strictly negative real part. Any solution $x$ for system (1) is a
stochastic process with mean $0$ and covariance matrix
$\Gamma=\mathbf{E}(xx^{T})$ (see for example Section $4.3$ in[13]).

In a network modeling setting, $A$ is interpreted as a weighted and signed
adjacency matrix. A non-zero element $A_{ij}\neq 0$ is interpreted as the
existence of a directed edge from node $j$ to node $i$. The sign of $A_{ij}$
determines the nature of the interaction (excitatory or inhibitory) and
$|A_{ij}|$ determines its strength.

##  4 Solving the covariance Lyapunov equation for the state matrix

Figure 1: Heatmaps for three examples of weighted connectivity matrices of
dimension $8\times 8$. The leftmost heatmap is for a sparse matrix
$A\in\mathbb{R}^{8\times 8}$ generated randomly using the algorithm in Section
8. The other two matrices were selected randomly from the solution space
$\mathcal{S}_{\Gamma}$ for the matrix $A$. This means the solution to the
system in (1) has the same covariance matrix for all three matrices.

It is known [12, 13] that $A$ and $\Gamma$ satisfy the following Lyapunov
equation:

$\Gamma A^{T}+A\Gamma=-I.$ (2)

Given $A$, the stable covariance matrix solution can be computed by

$\text{vec}(\Gamma)=-(I\otimes A+A\otimes I)^{-1}\text{vec}(I).$

However, because the covariance matrix is symmetric, the inverse problem,
i.e., solving for $A$ given $\Gamma$, does not have a unique solution [14].
Following [14], given $\Gamma$, define its orthonormal spectral decomposition:

$\Gamma=UCU^{T}$ (3)

where $U$ is an orthonormal matrix and $C$ is a diagonal matrix of entries
$c_{i}$, the eigenvalues of $\Gamma$. Let $\bar{A}=U^{T}AU$. Then we can
rewrite (2) as

$UCU^{T}\\!A^{T}+AUCU^{T}=C\bar{A}^{T}+\bar{A}C=-I$

which has solutions $\bar{A}$ easily shown to satisfy

$\bar{A}_{i,j}=\begin{cases}\frac{-1}{2c_{i}},&\text{if }i=j\\\
-\frac{c_{i}}{c_{j}}\bar{A}_{j,i},&\text{if }i\neq j\end{cases}.$ (4)

The set of matrices $\bar{A}$ satisfying (4) is an affine subspace of
dimension $m=\frac{n(n-1)}{2}$. Since $A=U\bar{A}U^{T}$, this means that the
set of possible solutions $A$ to the inverse covariance Lyapunov equations is
also an $m$-dimensional affine space
$\mathcal{S}_{\Gamma}\subseteq\mathbf{R}^{n\times n}$. Figure 1 shows a
Hurwitz matrix $A$, with correlation matrix $\Gamma$, together with other two
matrices taken randomly from the solution space $\mathcal{S}_{\Gamma}$, hence
associated to the same covariance matrix.

The following proposition characterizes the matrices in $\mathcal{S}_{\Gamma}$
with a linear equality constraint on the vectorized matrices. It is needed to
formulate an $L_{1}$-regularization problem over $\mathcal{S}_{\Gamma}$ as a
LP problem.

###### Proposition 4.1

Given a covariance matrix $\Gamma=UCU^{T}$, define a matrix $\mathbf{M}$ of
dimensions $\frac{n(n+1)}{2}\times n^{2}$ and a vector $\mathbf{b}$ of
dimension $\frac{n(n+1)}{2}$ with entries, respectively, given by

$\mathbf{M}_{(i,j)(\ell,k)}=\begin{cases}c_{j}U_{\ell,i}U_{k,j}+c_{i}U_{\ell,j}U_{k,i}&\text{if
}i\neq j\\\ U_{\ell,i}U_{k,j}&\text{if }i=j\end{cases}$

and

$\mathbf{b}_{(i,j)}=\begin{cases}0&\text{if }i\neq j\\\
\frac{-1}{2c_{i}}&\text{if }i=j\end{cases}$

where we use $(i,j)$ to denote the indexes of the vectorization of the upper
triangle of $\bar{A}$ (including the diagonal) and $(\ell,k)$ the indexes of
the vectorization of the full matrix. Then for $v\in\mathbb{R}^{n^{2}}$, we
have that $\text{vec}^{-1}(v)\in\mathcal{S}_{\Gamma}$ if and only if
$\mathbf{M}v=\mathbf{b}$.

######  Proof 4.2.

Let $v\in\mathbb{R}^{n^{2}}$ and take $A=\text{vec}^{-1}(v)$. Suppose
$A\in\mathcal{S}_{\Gamma}$. From (4), if $i\neq j$ then
$\sum_{\ell=1}^{n}\sum_{k=1}^{n}U_{\ell,i}A_{\ell,k}U_{k,j}=(U^{T}AU)_{i,j}=\bar{A}_{i,j}=-\frac{c_{i}}{c_{j}}\bar{A}_{j,i}=-\frac{c_{i}}{c_{j}}\sum_{\ell=1}^{n}\sum_{k=1}^{n}U_{\ell,j}A_{\ell,k}U_{k,i}$,
from which it follows that

$\sum_{\ell=1}^{n}\sum_{k=1}^{n}(c_{j}U_{\ell,i}U_{k,j}+c_{i}U_{\ell,j}U_{k,i})A_{\ell,k}=0.$
(5)

Similarly, when $i=j$,

$\bar{A}_{i,j}=\sum_{\ell=1}^{n}\sum_{k=1}^{n}U_{\ell,i}U_{k,j}A_{\ell,k}=\frac{-1}{2c_{i}}.$
(6)

Equations (5),(6) are precisely the $\frac{n(n+1)}{2}$ identities that are
encoded in $\mathbf{M}$ and $\mathbf{b}$, which implies that
$\mathbf{M}v=\mathbf{b}$.

Following the same argument, for any $v\in\mathbb{R}^{n^{2}}$, if
$\mathbf{M}v=\mathbf{b}$, then $\text{vec}^{-1}(v)\in\mathcal{S}_{\Gamma}$.

##  5 $L_{1}$-regularization on $\mathcal{S}_{\Gamma}$ and sparse network
reconstruction

Assume that the interaction network we are reconstructing is sparse. Then, a
reasonable way to recover a particular solution from $\mathcal{S}_{\Gamma}$ is
to look for matrices with minimum $L_{1}$ norm; this is a common approach for
promoting sparsity of solutions [15]. We pose the problem of minimizing the
$L_{1}$ norm of the vectorized matrices as follows:

Minimize $\displaystyle\lVert v\rVert_{1}$ (7) Subject to
$\displaystyle\mathbf{M}v=\mathbf{b}\,.$

In turn, (7) can be transformed into a Linear Programming (LP) problem by
taking a new variable $u\in\mathbb{R}^{n^{2}}$ and a vector
$c=(\mathbf{1}_{n^{2}},\mathbf{0}_{n^{2}})$, and defining the LP problem:

Minimize $\displaystyle c^{T}$ $\displaystyle\begin{pmatrix}u\\\
v\end{pmatrix}$ (8) Subject to
$\displaystyle\begin{bmatrix}\mathbf{0}&\mathbf{M}\end{bmatrix}$
$\displaystyle\begin{pmatrix}u\\\ v\end{pmatrix}=\mathbf{b}$ and
$\displaystyle\begin{bmatrix}-I&I\\\ -I&-I\end{bmatrix}$
$\displaystyle\begin{pmatrix}u\\\ v\end{pmatrix}\leq\mathbf{0}_{2n^{2}}.$

The LP problem (8) aims at minimizing the objective $\sum_{(i,j)}u_{(i,j)}$
subject to the restriction that $\text{vec}^{-1}(v)\in\mathcal{S}_{\Gamma}$
and $\lvert v_{(i,j)}\rvert\leq u_{(i,j)}$ for all $i,j\in[n]$. A solution to
the LP problem (8) immediately gives a solution to the problem (7) and vice-
versa – in this sense the two problems are equivalent.

Solving (8) will return a sparse solution from $\mathcal{S}_{\Gamma}$.
However, because there exist multiple sparse solutions in
$\mathcal{S}_{\Gamma}$, the returned sparse solution might still be very
different from the true network adjacency matrix, mostly depending on the
initial problem data. In the following section we present a way to constrain
the optimization problem by including prior approximate knowledge on edge
existence to bias the reconstruction toward solutions that are consistent with
the priors.

##  6 Including priors on edge existence

Figure 2: Diagram illustrating the way the optimization problem (7) can be
encoded as a linear programming problem. The top $\frac{n(n+1)}{2}\times
2n^{2}$ sub-matrix is used as an equality constraint, which restricts the
search to matrices on $\mathcal{S}_{\Gamma}$. The $2n^{2}\times 2n^{2}$ sub-
matrix bellow is used as an inequality constraint which ensures that for each
$\ell,k$ we have $\lvert v_{(\ell,k)}\rvert\leq u_{(\ell,k)}$. An example of
this encoding for the case $n=5$ is show on the right.

The idea for including priors comes from the observation that if we knew that
exactly $p$ directed edges (and which ones) existed in the network, then $A$
would lie in $\mathcal{R}_{\Gamma}\subseteq\mathbf{R}^{n\times n}$ of
dimension $p$, i.e., the subspace parameterized by the $p$ nonzero elements of
$A$. By Proposition 4.1, $A\in\mathcal{S}_{\Gamma}$. Thus,
$A\in\mathcal{S}_{\Gamma}\cap\mathcal{R}_{\Gamma}$, that is, $A$ must lie in
the intersection of two affine subspaces of dimension
$m=\dim(\mathcal{S}_{\Gamma})=\frac{n(n-1)}{2}$ and
$p=\dim(\mathcal{R}_{\Gamma})$, respectively.

It is well known (a consequence of Theorem 2.43 in[16]) that the transversal
intersection of two linear subspaces of $\mathbb{R}^{n\times n}$ of dimension
$p$ and $m$, with $m+p\leq n^{2}$ is either empty or a point. This means that
if we have exact knowledge of which edges exist in the network and the network
is sparse enough (i.e., $m+p\leq n^{2}$), then solving (8) restricted to
$\mathcal{R}_{\Gamma}$ would return $A$ exactly. However, given only imperfect
knowledge of edge existence and if $m+p<n^{2}$ (which is the case for
moderately sparse networks), then our noisy approximation
$\hat{\mathcal{R}}_{\Gamma}$ of $\mathcal{R}_{\Gamma}$ and
$\mathcal{S}_{\Gamma}$ will almost surely not intersect at all. In spite of
this, looking for the matrix $A\in\mathcal{S}_{\Gamma}$ with minimal distance
to $\hat{\mathcal{R}}_{\Gamma}$ should bias the solution (8) toward the real
$A$. This is the approach we use here.

Based on this idea we define a vector $Z\in[0,1]^{n^{2}}$ with entries
representing the relative importance assigned to each connection during the
optimization. The objective of the minimization then becomes
$\sum_{(i,j)}Z_{(i,j)}\lvert v_{(i,j)}\rvert$. In the simplest case, we can
introduce information about the presence of edges in the following way. Let
$\mathcal{I}=\\{(i,j)\in[n]^{2}\mid(i,j)\text{ is a known edge}\\}$. Then we
can define $Z$ as

$Z_{(i,j)}=\begin{cases}1&\text{if }(i,j)\notin\mathcal{I}\\\
0&\text{otherwise.}\end{cases}$

Written as an LP the problem becomes

Minimize $\displaystyle c^{T}$ $\displaystyle\begin{pmatrix}u\\\
v\end{pmatrix}$ (9) Subject to
$\displaystyle\begin{bmatrix}\mathbf{0}&\mathbf{M}\end{bmatrix}$
$\displaystyle\begin{pmatrix}u\\\ v\end{pmatrix}=\mathbf{b}$ and
$\displaystyle\begin{bmatrix}-I&\text{diag}(Z)\\\
-I&-\text{diag}(Z)\end{bmatrix}$ $\displaystyle\begin{pmatrix}u\\\
v\end{pmatrix}\leq\mathbf{0}_{2n^{2}}.$

When there are no edge priors, $Z=\mathbf{1}_{n^{2}}$, and the problem in (9)
reduces to (8). An illustrative example of the constraint matrix in (9) is
shown in Figure 2. Note in Figure 2 that this matrix is sparse in most places
except the top right corner; thus, optimization methods that take advantage of
sparse structure can be employed. Problem (9) leads to an optimization that
prioritizes finding a solution where the edges not in $\mathcal{I}$ have
weight close to zero in absolute value. The values of $Z$ could also be
adjusted to correspond with the level of certainty about prior edge existence.
For simplicity, in the following we only consider $Z\in\\{0,1\\}^{n^{2}}$.

##  7 Edge priors from Transfer Entropy

There are various ways to obtain prior knowledge on edge existence, e.g., from
expert knowledge or from previous analysis. One generally applicable tool for
inferring the existence of directed interactions is Transfer Entropy (TE)[4].
Given two discrete-time stationary stochastic processes $X$ and $Y$, the TE at
$T_{X\to Y}$ from $X$ to $Y$ is a measure of the predictive power of $X$ about
$Y$. In its simplest form $T_{X\to Y}({\tt t})$, the transfer entropy $T_{X\to
Y}$ at (discrete) time ${\tt t}$, can be defined as [4]

$\displaystyle T_{X\to Y}({\tt t})=I(X({\tt t}-1);Y({\tt t})\mid Y({\tt
t}-1))$ $\displaystyle=H(Y({\tt t})\mid Y({\tt t}-1))-H(Y({\tt t})\mid X({\tt
t}-1),Y({\tt t}-1)).$

So, $T_{X\to Y}(\tt t)$ is the mutual information $I$ of $X({\tt t}-1)$ and
$Y({\tt t})$ conditioned on $Y({\tt t}-1)$, where

${\scriptstyle I(X;Y\mid
Z)=\int_{\mathcal{Z}}\int_{\mathcal{Y}}\int_{\mathcal{X}}p_{X,Y,Z}(x,y,z)\ln\left(\frac{p_{Z}(z)p_{X,Y,Z}(x,y,z)}{p_{X,Z}(x,z)p_{Y,Z}(y,z)}\right)dx\;dy\;dz},$

$p$ are probability density functions of the joint distributions of variables
represented by the subscripts, and $\mathcal{X},\mathcal{Y},\mathcal{Z}$ are
the supports of $X,Y,Z$ respectively. $T_{X\to Y}({\tt t})$ can equivalently
be written in terms of $H(X\mid
Y)=-\int_{\mathcal{X}}\int_{\mathcal{Y}}p_{X,Y}(x,y)\ln(\frac{p_{X,Y}(x,y)}{p_{Y}(y)})$
. If the processes are assumed to be stationary then TE is the same for all
values of $\tt t$ and we can simply write $T_{X\to Y}$.

This measure has been shown to be a good indicator of directed interactions
between pairs of noisy dynamical variables [17, 18, 7], and can be seen as a
nonlinear generalization of Granger causality [19]. It can also be extended to
take into account factors such as redundancy and synergy in a partial
information decomposition approach [20].

A simple way to reduce the effects of redundancy when inferring connectivity
is to use conditional TE: $T_{X\to Y\mid Z}$. The definition of $T_{X\to Y\mid
Z}$ is the same as for $T_{X\to Y}$ but conditioned on the past of $Z$.
Connectivity can then be inferred from a set of $n$ stochastic processes
$X_{i}$ by calculating $T_{X_{i}\to X_{j}\mid X_{(i,j)}}$ for each pair $1\leq
i,j\leq n$, where $X_{(i,j)}$ is the joint distribution of all the variables
except $X_{i}$ and $X_{j}$. Then we say there is a significant interaction
from $X_{i}$ to $X_{j}$ if $T_{X_{i}\to X_{j}\mid X_{(i,j)}}$ is higher than
what would be expected by pure chance (using suitable data shuffling and
significance testing). However, this approach is usually not feasible for
large networks due to the amount of required data.

To bypass this problem in cases where the number of edges in the network is
small (i.e., the connectivity matrix is sparse), Novelli et al. [7] proposed a
greedy algorithm that finds a set of sources for each target node by i)
creating a candidate set of source nodes with significant TEs when conditioned
only on previously selected nodes and ii) removing all nodes for which TE
became non-significant due to redundancy with newly added nodes. This
algorithm (and others) is implemented in the IDTxl Python package [21].

For the purpose of testing the contribution of edges inferred with TE to our
method while keeping the inference fast, we adapted the greedy algorithm in
[7] to a simplified version where only Step i) of the algorithm is used. This
did not seem to drastically impact the performance of the method. However, we
observed an increase in false positives, so we introduced a strict upper bound
on the number of inferred edges.

##  8 Numerical validation

Figure 3: Three examples of reconstructed connected networks using our method
with edge priors inferred using TE (middle), and no info (right), applied to
time-series generated from the weakly-nonlinear system in (10). The ground
truth connectivity matrix $A$ is show on the left. The top row shows examples
of good reconstruction (high alignment between reconstructed matrix and the
ground truth), the middle row shows reconstruction with median alignment, and
the bottom row shows a bad reconstruction (low alignment). The alignments for
the reconstructions with TE Info were $0.99$, $0.90$ and $0.31$ for the good,
median, and bad respectively. For the No Info the alignments were $0.43$,
$0.42$, and $0.53$ for the good, median, and bad respectively. Examples were
selected from $600$ simulated dynamics of matrices with $20$ edges and
different $\varepsilon$ values by sorting according to alignment of TE Info
reconstruction and selecting the worst, median, and best reconstructions.

###  8.1 Generating random sparse Hurwitz matrices

Algorithm 1 presents the pseudo-code we used for generating random Hurwitz
matrices. The algorithm produces a matrix that has the form

$A=-I+\frac{1-\varepsilon}{b_{max}}B\,,$

where $B$ is is an Erdős–Rényi graph with normally distributed edge weights,
$\varepsilon\in(0,1]$ is a parameter that controls the spectrum of $A$ by
weighting $B$, and $b_{max}=\max\\{\Re(\lambda)\mid\lambda\in\sigma(B)\\}$. We
get $a_{max}=\max\\{\Re(\lambda)\mid\lambda\in\sigma(A)\\}=-1+\varepsilon$.

Algorithm 1 Random Hurwitz

$n\in\mathbb{N},M\in[n(n-1)],\varepsilon\in[0,1]$

$A$

$G=(V,E)\leftarrow$ Erdős–Rényi $G(n,M)$ random digraph

while 1 do

$i,j\leftarrow 0,0$

while $i<n$ do

while $j<n$ do

if $(i,j)\in E$ then

$B[i,j]\leftarrow$ Sample $\mathcal{N}(0,1)$ distribution

else

$B[i,j]\leftarrow 0$

end if

$i\leftarrow i+1$

end while

$j\leftarrow j+1$

end while

$b_{max}\leftarrow\max\\{\Re(\lambda)\mid\lambda\in\sigma(B)\\}$

if $b_{max}\neq 0$ then

break

end if

end while

$A\leftarrow-I+\frac{1-\varepsilon}{b_{max}}B$

Figure 4: Plots showing the performance of our method for $100$ samples of
random Hurwitz matrices of size $10\times 10$ generated with different values
of $\varepsilon$, and with a) $10$, b) $20$, c) $30$ edges. The $L_{1}$
optimization methods compared are: Full Info (blue), TE Info (red), No Info
(green) on edge existence. Performance of precision and correlation matrices
were added as reference in purple and orange respectively. Darker colors
correspond to reconstructions for data simulated using the linear system in
(1), and lighter colors for the weakly-nonlinear system in (10). Notches in
boxes represent median values and dotted lines mean values. Boxes encompass
$50\%$ of the data points. Isolated points are outliers.

###  8.2 Implementation

For numerical validation, our algorithm was implemented in standard Python
libraries. The code can be found at https://github.com/ianxul/SDE-net-
reconstruction. For estimating conditional TE interactions, we used the GPU-
enabled estimator in IDTxl package [21], and the adapted algorithm described
in Section 7. We further simplified the permutation-based significance test
suggested in [7] by using a less computationally intensive threshold heuristic
similar to [18]. $L_{1}$-optimization was performed using CVXPY package [22]
with the splitting conic solver (SCS).

Simulations of SDEs were run with Julia’s DifferentialEquations solver. We
used the LambaEM solver for SDEs with a step size of $0.1$ for $10,000$ time
steps (giving $100,000$ data points for each simulation). We applied our
method to the data generated from the linear SDE system (1) and from the
weakly nonlinear (saturated network interactions) SDE system

$\frac{dx_{i}}{dt}=A_{i,i}x_{i}+\sum_{i\neq j}(\tanh(A_{i,j}x_{j}))+w(t).$
(10)

To compare different methods we computed the alignment between the vectorized
matrices, excluding the diagonal, as it is not related to network
reconstruction:

$\text{align}(A,B)=\frac{\sum_{\begin{subarray}{c}i\neq
j\end{subarray}}A_{i,j}B_{i,j}}{\left(\sum_{\begin{subarray}{c}i\neq
j\end{subarray}}A_{i,j}^{2}\right)^{\frac{1}{2}}\left(\sum_{\begin{subarray}{c}i\neq
j\end{subarray}}B_{i,j}^{2}\right)^{\frac{1}{2}}}.$ (11)

We compared three cases: i) “Full Info”, in which full information on edge
existence is given and which should lead to perfect reconstruction; ii) “TE
Info”, in which edge existence is inferred using TE methods; iii) “No Info”,
in which we simply perform $L_{1}$-regularization over $\mathcal{S}_{\Gamma}$
as in (8). Results are exemplified in Figure 3 and summarized in and 4.

###  8.3 Results and discussion

Our results show that adding edge existence priors obtained through TE [7] to
our reconstruction method improves the alignment of reconstructions
considerably when compared against doing the optimization with no prior
information, and against the precision and correlation matrices, as can be
seen in Figures 3 and 4. Interestingly, the optimization with no edge priors
actually performed worse than the symmetric methods, which stresses the
importance of introducing priors on edge existence. The above was true for
both the linear and weakly nonlinear cases.

All methods performed increasingly worse as the ground truth solution $A$
became less sparse or as $\varepsilon$ became smaller (i.e., as the spectrum
of $A$ got closer to the imaginary axis). This could simply be a result of not
having an optimal algorithm for inferring edges using TE, since the
performance of the method with full prior knowledge of existing edges (“Full
Info”) is mostly unaffected by changes in $\varepsilon$ and edge number.
Applying the full IDTxl method[7] could improve results further due to more
rigorous significance tests, a redundant edge cleanup pass and no hard limit
on inferred edges. The mean and median performance of the “TE Info” method was
always strictly better than all other methods we tested (apart, of course,
from “Full Info”) by a significant margin (bootstrap test $p<10^{-5}$).

Another interesting observation is that introducing a weak nonlinearity in the
model usually led to only minor changes in the median performance but often
drastically reduced the performance variance, and in some cases increased the
median performance as well. In other words, our method performed more
consistently (and sometimes better) in the presence of weakly nonlinear
network interactions as compared to a purely linear network model. This effect
cannot be explained by the use of nonlinear edge inference methods like TE,
since fully linear methods like “No Info” and those based on precision and
correlation matrices also benefited from the presence of weakly nonlinear
interactions. We will investigate this interesting phenomenon in future
research.

##  9 Conclusions and perspectives

We introduced a fast and high performing method to reconstruct directed and
weighted networks and analyzed its performance using both linear and weakly
nonlinear network models. Future works will aim at improving the heuristics
used for the TE inference step. Theoretically it will also be important to
understand the role of nonlinearities on network inference, which might be key
for application to (usually nonlinear) neuronal and other kind of biological
networks. Measures of the intrinsic timescale of each node, estimated through
auto-correlation analysis [23], can further be used to further constraint the
$L_{1}$-optimization step. This will also require consideration of the role of
network self-loops, i.e., the diagonal elements of $A$, more explicitly in the
method. All these ideas will soon be implemented and tested on experimental
neuroscience (EEG) datasets.

## References

  * [1] R. Liégeois, A. Santos, V. Matta, D. V. D. Ville, and A. H. Sayed, “Revisiting correlation-based functional connectivity and its relationship with structural connectivity,” _Network Neuroscience_ , vol. 4, no. 4, p. 1235–1251, 2020.
  * [2] T. W. Lin, A. Das, G. P. Krishnan, M. Bazhenov, and T. J. Sejnowski, “Differential covariance: A new class of methods to estimate sparse connectivity from neural recordings,” _Neural Computation_ , vol. 29, no. 10, p. 2581–2632, 2017.
  * [3] R. Mohanty, W. A. Sethares, V. A. Nair, and V. Prabhakaran, “Rethinking measures of functional connectivity via feature extraction,” _Scientific Reports_ , vol. 10, no. 1, p. 1298, 2020.
  * [4] T. Schreiber, “Measuring information transfer,” _Physical Review Letters_ , vol. 85, no. 2, p. 461–464, Jul. 2000.
  * [5] M. Lobier, F. Siebenhühner, S. Palva, and J. M. Palva, “Phase transfer entropy: A novel phase-based measure for directed connectivity in networks coupled by oscillatory interactions,” _NeuroImage_ , vol. 85, p. 853–872, 2014.
  * [6] M. Ursino, G. Ricci, and E. Magosso, “Transfer entropy as a measure of brain connectivity: A critical analysis with the help of neural mass models,” _Frontiers in Computational Neuroscience_ , vol. 14, 2020.
  * [7] “Large-scale directed network inference with multivariate transfer entropy and hierarchical statistical testing,” vol. 3, p. 827–847, 2019.
  * [8] N. M. Timme and C. Lapish, “A tutorial for information theory in neuroscience,” _eneuro_ , vol. 5, no. 3, pp. ENEURO.0052–18.2018, 2018.
  * [9] P. Sharma, D. J. Bucci, S. K. Brahma, and P. K. Varshney, “Communication network topology inference via transfer entropy,” _IEEE Transactions on Network Science and Engineering_ , vol. 7, no. 1, p. 562–575, 2017.
  * [10] K. J. Friston, L. Harrison, and W. Penny, “Dynamic causal modelling,” _Neuroimage_ , vol. 19, no. 4, pp. 1273–1302, 2003.
  * [11] U. Casti, G. Baggio, D. Benozzo, S. Zampieri, A. Bertoldo, and A. Chiuso, “Dynamic brain networks with prescribed functional connectivity,” in _2023 62nd IEEE Conference on Decision and Control (CDC)_. IEEE, 2023, pp. 709–714.
  * [12] L. Socha, _Linearization methods for stochastic dynamic systems_. Springer Science & Business Media, 2007, vol. 730.
  * [13] S. Särkkä and A. Solin, _Applied Stochastic Differential Equations_ , 1st ed., ser. Institute of Mathematical Statistics textbooks. Cambridge University Press, 2019, vol. 10.
  * [14] K. Fernando and H. Nicholson, “Solution of lyapunov equation for the state matrix,” _Electronics Letters_ , vol. 17, no. 5, pp. 204–205, 1981.
  * [15] E. Candes and J. Romberg, “l1-magic: Recovery of sparse signals via convex programming,” _URL: www. acm. caltech. edu/l1magic/downloads/l1magic. pdf_ , vol. 4, no. 14, p. 16, 2005.
  * [16] S. Axler, _Linear algebra done right_. Springer Nature, 2023.
  * [17] T. Bossomaier, L. Barnett, M. Harré, and J. T. Lizier, _An Introduction to Transfer Entropy_. Cham: Springer International Publishing, 2016\.
  * [18] A. Rahimzamani and S. Kannan, “Network inference using directed information: The deterministic limit,” in _2016 54th Annual Allerton Conference on Communication, Control, and Computing (Allerton)_. Monticello, IL, USA: IEEE, 2016, p. 156–163.
  * [19] L. Barnett, A. B. Barrett, and A. K. Seth, “Granger causality and transfer entropy are equivalent for gaussian variables,” _Physical Review Letters_ , vol. 103, no. 23, p. 238701, 2009.
  * [20] P. L. Williams and R. D. Beer, “Generalized measures of information transfer,” no. arXiv:1102.1507, 2011, arXiv:1102.1507 [physics].
  * [21] P. Wollstadt, J. T. Lizier, R. Vicente, C. Finn, M. Martínez-Zarzuela, P. Mediano, L. Novelli, and M. Wibral, “Idtxl: The information dynamics toolkit xl: a python package for the efficient analysis of multivariate information dynamics in networks,” _Journal of Open Source Software_ , vol. 4, no. 34, p. 1081, 2019, arXiv:1807.10459 [cs, math].
  * [22] S. Diamond and S. Boyd, “CVXPY: A Python-embedded modeling language for convex optimization,” _Journal of Machine Learning Research_ , vol. 17, no. 83, pp. 1–5, 2016.
  * [23] R. Rossi-Pool, A. Zainos, M. Alvarez, S. Parra, J. Zizumbo, and R. Romo, “Invariant timescale hierarchy across the cortical somatosensory network,” _Proceedings of the National Academy of Sciences_ , vol. 118, no. 3, p. e2021843118, 2021.


# Computational Power of a Single Oblivious Mobile Agent in Two-Edge-Connected
Graphs

Taichi Inoue† Naoki Kitamura† Taisuke Izumi† Toshimitsu Masuzawa†

$\dagger$ Osaka University, 1-5, Yamadaoka, Suita, Osaka, 565-0871, Japan

###### Abstract

We investigated the computational power of a single mobile agent in an
$n$-node graph with storage (i.e., node memory). Generally, a system with one-
bit agent memory and $O(1)$-bit storage is as powerful as that with $O(n)$-bit
agent memory and $O(1)$-bit storage. Thus, we focus on the difference between
one-bit memory and oblivious (i.e., zero-bit memory) agents. Although their
computational powers are not equivalent, all the known results exhibiting such
a difference rely on the fact that oblivious agents cannot transfer any
information from one side to the other across the bridge edge. Hence, our main
question is as follows: Are the computational powers of one-bit memory and
oblivious agents equivalent in 2-edge-connected graphs or not? The main
contribution of this study is to answer this question under the relaxed
assumption that each node has $O(\log\Delta)$-bit storage (where $\Delta$ is
the maximum degree of the graph). We present an algorithm for simulating any
algorithm for a single one-bit memory agent using an oblivious agent with
$O(n^{2})$-time overhead per round. Our results imply that the topological
structure of graphs differentiating the computational powers of oblivious and
non-oblivious agents is completely characterized by the existence of bridge
edges.

##  1 Introduction

###  1.1 Background and Our Result

A _mobile agent_ (hereinafter called an _agent_) is an individual entity that
performs a given task by autonomously moving in a graph (or network). This is
one of the main computational paradigms of distributed algorithms. In the
theory of mobile agent systems, there exist various models that differ in
memory resources, asynchrony, observation capability of the system, and so on.
Revealing the computational power of each model is recognized as a central
question in this research field. This study focuses on the computational power
of a system with a single agent, despite that it is fairly commonplace to
consider the cooperation of multiple agents.

In single-agent systems, the amount of (persistent) memory held by the agent
and nodes is a major quantitative parameter of their computational capability.
The computational cost is measured by _rounds_ (i.e., the number of movements
by the agent). Throughout this paper, we refer to the memory of the agent as
_memory_ and that of each node as _storage_. It is almost evident that an
agent with sufficiently large memory can simulate any centralized algorithm.
That is, any computable problem can be solved. Hence, theoretical interest
lies in problem solvability when the amount of memory is limited. For example,
the graph exploration problem, which requires the agent to visit all nodes in
the graph, is a fundamental problem Generally, $\Theta(\log n)$-bit memory is
necessary and sufficient to solve this problem when the nodes have no storage
[5, 10]. It is also proved that the system with $O(1)$-bit memory and
$O(1)$-bit storage can solve the graph exploration problem [1].

In this study, we investigated the effect of the amount of memory on problem
solvability. A known result on this research line is that, in any $n$-node
graph with $O(1)$-bit storage per node, the agent with one-bit memory is as
powerful as that with $O(n)$-bit memory [6]. More precisely, any property of
the graph $G$ decidable by the $O(n)$-bit memory agent within polynomial
movements and polynomial-time local computation is also decidable by the one-
bit memory agent within polynomial movements and polynomial-time local
computation. This result is not limited to decision problems, but actually
provides a general technique for simulating the execution of any $O(n)$-bit
memory agent using a one-bit memory agent with a polynomial-time
multiplicative overhead per round. It has also been shown that the
computational powers of the one-bit and zero-bit (i.e., oblivious) memory
agents are inherently different regardless of the amount of available storage.
Thus, our question is already closed in general settings. However, whether the
separation between the one-bit memory and oblivious agents is exhibited in a
restricted graph class remains unclear. All known results exhibiting such a
separation [1, 6] rely on the existence of a bridge edge (i.e., a single edge
such that its removal disconnects the graph) in the graph. More precisely,
they are derived from the fact that the oblivious agent cannot transfer any
information from one side to the other side across the bridge edge, whereas
the one-bit memory agent can. Therefore, our central question is then
rephrased as: Are the computational powers of the one-bit memory and oblivious
agents equivalent in 2-edge-connected graphs or not? The main contribution of
this study is to answer this question positively. We focus on 2-edge-connected
graphs with a maximum degree $\Delta$ and relax the constraint on the amount
of storage from $O(1)$ bits to $O(\log\Delta)$ bits. In this setting, we
present a polynomial-time overhead algorithm that simulates the execution of a
single one-bit memory agent by an oblivious agent. By combining the results of
[6], we can deduce the equivalence between an $O(n)$-bit memory agent and an
oblivious agent in 2-edge-connected graphs. This implies that the topological
structure of graphs differentiating the computational powers of oblivious and
non-oblivious agents is completely characterized by the existence of bridge
edges. The authors believe that this result provides a sharp insight into the
computational complexity theory of mobile agents.

###  1.2 Technical Idea

The model considered in this study follows the standard assumptions on mobile
agent systems. The graph $G$ is _anonymous_ (i.e., the agent cannot refer to
the unique IDs of nodes), and the neighbors of a node are identified by the
_local port numbers_ assigned to the edges incident to the node. When an agent
enters a node, it recognizes the _entry port number_ (assigned to the edge
used to visit the current node). In one round, the agent performs local
computation, which includes updating the information stored in its own memory
and the storage at the current node, and decides the _outgoing port number_
(assigned to the edge used to leave the node).

The main technical issue in simulating a one-bit memory agent is how we can
transfer the information to an oblivious agent. We resolve this by utilizing
information on entry port numbers. To clarify our idea, we first consider the
simple case in which the graph is an oriented cycle and assume that the agent
at a node $s$ wants to transfer one-bit information to the neighbor $t$ of
$s$. There are two distinct paths from $s$ to $t$ (i.e., clockwise and
counterclockwise, specified by the orientation), which result in different
entry port numbers for $t$. The agent can transfer an information bit
$b\in\\{0,1\\}$ from $s$ to $t$ using the path ending up with port number $b$.

When the graph topology is arbitrary, the simulation algorithm becomes more
complicated; however, the fundamental idea is the same. The algorithm first
finds a cycle $C$ of $G$ containing edge $(s,t)$, which we refer to as the
_information transfer cycle (ITC)_ , to transfer one-bit information from node
$s$ to its neighbor $t$. The algorithm provides a consistent orientation to
the ITC and applies the algorithm above for oriented cycles to the ITC.
Because we assume that $G$ is 2-edge-connected, there necessarily exists an
ITC for any edge $(s,t)$ in $G$.

Our algorithm runs a depth-first search (DFS) to compute ITC. The agent starts
DFS from $s$ with the choice of $(s,t)$ as the first traversal edge. Because
$G$ is 2-edge-connected, the agent eventually reaches $s$ again through edge
$e$ different from $(s,t)$. Figure 1 shows an example of transmission on an
ITC.

Figure 1: Example of the construction of an ITC (drawn by bold lines) on a DFS
tree and imitative transmission of one-bit data. Arrows are moving directions
of the agent. Some local port numbers are omitted.

Let $P_{s,t}$ be the path from $s$ to $t$ managed by the DFS algorithm. Then,
the algorithm obtains the ITC $P_{s,t}+e$. The agent must reset all
information because the garbage information is left at the nodes that are
traversed by the DFS process but not contained in the constructed ITC. It is
implemented by careful re-execution of the DFS starting from $s$ with the
first traversal edge $(s,t)$.

We emphasize that its implementation is far from triviality, although the
intuition of our algorithm stated above is simple and easy to follow. A
technical hurdle is that the agent itself is oblivious. The agent cannot
memorize the subtask currently executed despite our algorithmic idea being
constituted of several subtasks. Our algorithm conducts the sequential phase-
by-phase composition of all subtasks carefully, using only node storage.
Details of the design are presented in Section 3.

###  1.3 Related Work

To the best of our knowledge, the authors’ prior work [6] is the first to
consider the effect of memory size on the solvability of general tasks in
graphs with storage, but several studies have been conducted on specific
problems. One benchmark problem is the graph exploration problem. In the case
where nodes have no storage, it has been shown that $\Theta(\log n)$-bit
memory is necessary and sufficient to solve it within polynomial time [5, 10].
When allowing nodes to be stored, the graph exploration algorithm can be
solved by an oblivious agent using $O(\log\Delta)$-bit storage per node (where
$\Delta$ is the maximum degree of the graph) [11]. Minimizing the storage
size, there exists a graph exploration algorithm for an $O(1)$-bit memory
agent using $O(1)$-bit storage [1]. It also shows that exploration using a
single oblivious agent is impossible if the storage size is $O(1)$ bits. Note
that the topology used in their impossibility proof has a bridge edge; that
is, it is not 2-edge-connected. An interesting open problem inspired by our
result is whether an oblivious agent with $O(1)$-bit storage can solve the
graph exploration problem for 2-edge-connected graphs or not. It is possible
to explore 2-edge-connected graphs if one can construct the ITC using only
$O(1)$-bit storage because our simulation algorithm requires $\omega(1)$-bit
storage only during the construction of the ITC. There also exists a model in
which the agent uses a “pebble” device that can be put on and picked up from
nodes by the agent. Disser et al. [4] showed that $n$-node graph exploration
can be solved using $\Theta(\log\log n)$ pebbles. However, this method has the
disadvantage of being time inefficient since it takes $n^{O(\log\log n)}$
rounds to complete the exploration. Although it is a crucial assumption in our
simulation algorithm that the agent knows the entry port number, there is a
weaker model called the _myopic robot_ , in which the entry port number is
undetectable by agents [2, 7, 8, 9]. Although no formal proof is given, it is
almost trivial that such a weaker agent cannot simulate the agent memory as in
our result, even under the assumption of 2-edge-connectivity. While the model
and problem are significantly different, Dieudonne et al. [3] presented a
solution based on an approach similar to ours. In that study, the authors
considered the information transfer between the robots in the 2D plane, which
cannot have an explicit communication channel. In their approach, the
transferred information is not embedded into movement patterns as in our
approach but is embedded into the (real-value) distance between two robots.

##  2 Preliminaries

###  2.1 Graph

We used $[a,b]$ to denote the set of integers at least $a$ and at most $b$.
Let $G$ be a graph with $n$ nodes. This is formally defined as a port-numbered
graph $G=(V,E,\Pi)$, where $V$ is the set of nodes, $E$ is the set of edges,
and $\Pi$ is the set of port-numbering functions (explained later). Throughout
this paper, we assume that $G$ is simple, undirected, and 2-edge-connected.
Each node in $G$ is identified by a non-negative integer $i\ (0\leq i\leq
n-1)$. However, the agent operating in $G$ cannot see those values, that is,
$G$ is anonymous (the behavior of the agent is formally defined in Section
2.2). For $e\in E$, we define $G-e$ as a graph obtained by removing $e$ from
$G$. Note that $G-e$ is always connected because we assume that $G$ is 2-edge-
connected. The edges incident on each node $i$ are distinguished by _local
port numbers_. The _port numbering function_ at node $i$ is defined as
$\pi_{i}:[0,\Delta_{i}-1]\to N_{i}$, where $\Delta_{i}$ is the degree of node
$i$ and $N_{i}$ is the set of neighbors of $i$. The maximum degree of $G$ is
defined as $\Delta$. Note that $\Delta_{i}$ is necessarily greater than one
because $G$ is 2-edge-connected. We define $\pi^{-1}_{i}$ as the inverse
function of $\pi_{i}$. The set $\Pi$ consists of port-numbering functions for
all the nodes in $V$. Each node in $G$ has storage (i.e., node memory) that
keeps the stored information even after the agent leaves the node.

###  2.2 Mobile Agent

We consider a single-agent model in which one mobile agent moves in graph $G$.
A mobile agent has two distinct memory spaces: _temporary memory_ and
_persistent memory_. Temporary memory is a working space used for computation
at each node, but the stored information is completely reset when the agent
leaves the node. In contrast, persistent memory space retains the stored
information even when the agent moves from one node to another. In the
following argument, we use the terminology “(agent) memory” to refer to
persistent memory and measure the space complexity of the agent by the amount
of persistent memory. Although the size of the available temporary memory is
unbounded, $O(\log\Delta)$ bits of temporary memory are sufficient to
implement our algorithm. In this study, we focus on the _oblivious agent_ (or
the agent with zero-bit memory) and _one-bit agent_ (or the agent with one-bit
memory).

The execution of the agent follows discrete rounds $t=0,1,\cdots$. In each
round, the agent performed the following two computational steps:

  1. 1.

Let $i$ be the node where the agent currently stays. First, the agent starts
the local computation specified by the algorithm. At the beginning of the
local computation, the local port number corresponding to the edge through
which it has entered the current node $i$ (i.e., _entry port number_) and the
degree $\Delta_{i}$ of $i$ are stored in the temporary memory. Note that the
entry port number can be arbitrary at the beginning of the execution.
Following the information stored in the temporary memory, persistent memory,
and storage of $i$, the agent updates the storage of $i$ and its own
persistent memory. It also determines the port number corresponding to the
edge through which it leaves the node $i$ (i.e., _outgoing port number_).

  2. 2.

The agent moves to the neighbor of $i$ specified by the outgoing port number.
Note that the agent is guaranteed to arrive at the neighbor within the current
round.

Figure 2 illustrated the behavior of a single round.

Figure 2: Workflow of one-round operation (where $M$ and $M^{\prime}$ mean the
storage value of the node)

An algorithm $A$ for a one-bit agent is defined as
$A=(m,M,M^{\prime},l,\phi)$, a 5-tuple of an initial memory value $m$, an
initial storage value $M$ for each node, an initial storage value $M^{\prime}$
for the initial location of the agent, an initial location $l$ of the agent,
and a transition function $\phi$. Note that the special initialization value
$M^{\prime}$ is crucial for implementing the simulation because a symmetry-
breaking mechanism is required to distinguish the initial location of the
simulated agent from other nodes. The _transition function $\phi$_ for a one-
bit agent is defined as
$\phi:\mathbb{N}\times\mathbb{Z}_{\geq-1}\times\\{0,1\\}^{\ast}\times\left\\{0,1\right\\}\to\mathbb{Z}_{\geq-1}\times\\{0,1\\}^{\ast}\times\left\\{0,1\right\\}$,
where $\mathbb{Z}_{\geq-1}$ is a set of integers greater than or equal to -1.
The arguments given to $\phi$ are the degree of the node, entry port number,
storage value of the current node, and memory value. Note that the bit length
of the storage is not fixed by the algorithm because our model allows the
storage size to depend on the parameters of graph $G$. The returned values are
the outgoing port number, storage value to be left at the current node, and
memory value after local computation. Outgoing port number -1 implies that the
agent terminates the execution of the algorithm and stays at the same node.
For convenience, we consider an algorithm for an oblivious agent such that the
memory value given to and returned by $\phi$ is always 0. Note that $\phi$
does not consider the identifier of the current node as an argument because we
assume anonymous graphs.

Next, we define the system configuration and execution.

######  Definition 1 (configuration).

A _configuration $C$_ of the system is represented as
$C=\left((M_{0},\allowbreak M_{1},\allowbreak\dots,\allowbreak
M_{n-1}),\allowbreak m,\allowbreak
p,l\right)\in\left\\{\\{0,1\\}^{\ast}\right\\}^{n}\times\\{0,1\\}\times\mathbb{Z}_{\geq-1}\times[0,n-1]$,
where $M_{i}$ is the storage value of node $i$, $m$ is the memory value of the
agent, $p$ is the entry port number, and $l$ is the location of the agent. A
_valid configuration_ in $G$ is such that the value of the entry port number
is in the range $[-1,\Delta_{l}-1]$.

######  Definition 2 (execution).

Let $A=(m,M,M^{\prime},l,\phi)$ be an algorithm. Given two valid
configurations, $C_{t}=((M_{0,t},\dots,M_{n-1,t}),m_{t},p_{t},l_{t})$ and
$C_{t+1}=((M_{0,t+1},\allowbreak\dots,\allowbreak M_{n-1,t+1}),\allowbreak
m_{t+1},\allowbreak p_{t+1},\allowbreak l_{t+1})$, we consider that they
_follow_ the transition function $\phi$ of $A$ in $G$, denoted by
$C_{t}\xrightarrow{\phi,G}C_{t+1}$, if the following three conditions are
satisfied:

  * •

$\phi(\Delta_{l_{t}},p_{t},M_{l_{t},t},m_{t})=\left(\pi^{-1}_{l_{t}}(l_{t+1}),M_{l_{t},t+1},m_{t+1}\right)$

  * •

$M_{i,t+1}=M_{i,t}$ for all $i\neq l_{t}$

  * •

$p_{t+1}=\pi^{-1}_{l_{t+1}}(l_{t})$

Let $C$ be any valid configuration on $G$ such that the initial value of the
memory is $m$, the location of the agent is $l$, the initial storage value for
node $i\neq l$ is $M$ and $M^{\prime}$ for node $l$. The _execution
$E(G,C,A)$_ of the system is defined as an infinite sequence of configurations
$(C_{t})_{t\geq 0}$ such that $C_{0}=C$ and $C_{t}\xrightarrow{\phi,G}C_{t+1}$
holds for any $t\geq 0$.

In Definition 2, any execution is defined as an infinite sequence; however, if
the algorithm terminates in a finite round, then the execution is defined as
an infinite sequence such that $C_{t}=C_{t+1}=\dots$ holds for the termination
round $t$. As the transition function $\phi$ is assumed to be deterministic,
the execution of the algorithm is uniquely defined from the initial
configuration $C_{0}=C$. That is, $E(G,C,A)$ is uniquely defined. In addition,
throughout this study, we only consider algorithms that do not depend on the
initial entry port number. Then, execution $E(G,C,A)$ is determined only by
algorithm $A$, graph $G$, and initial location $l$ of the agent. Hence, we
refer to the execution $E(G,C,A)$ as $E(G,v,A)$ with the initial location
$v\in V$ of the agent.

###  2.3 Simulation

Let $\mathcal{A}(k,\lambda)$ be the set of all algorithms that utilize $k$-bit
memory and $\lambda$-bit storage. Note that $k$ and $\lambda$ are not
necessarily constant values, but might be functions that depend on the
parameters of the graph. The goal of this study was to design an algorithm
$A\in\mathcal{A}(0,\lambda)$ that simulates any algorithm
$A^{\ast}\in\mathcal{A}(1,\lambda^{\ast})$, where $\lambda$ and
$\lambda^{\ast}$ represent the storage sizes of the simulator and simulated
algorithms, respectively. To this end, we provide a formal definition for the
simulation of the algorithm. First, we present the notion of
$\gamma$-configurations.

######  Definition 3 ($\gamma$-configuration).

Let $\gamma=(\gamma_{M},\gamma_{A})$ be a pair of mappings,
$\gamma_{M}:\\{0,1\\}^{\lambda}\to\\{0,1\\}^{\lambda^{\ast}}$ and
$\gamma_{A}:\\{0,1\\}^{\lambda}\to\\{0,1\\}\times\mathbb{N}$. The _$\gamma$
-configuration $\gamma(C)$_ is defined as
$\gamma(C)=\left((\gamma_{M}(M_{0}),\gamma_{M}(M_{1}),\dots,\gamma_{M}(M_{n-1})\right),\allowbreak\gamma_{A}(M_{l}),l)$
for configuration $C=((M_{0},M_{1},\dots,\allowbreak M_{n-1}),\allowbreak
m,p,l)$.

Intuitively, the functions $\gamma_{M}$ and $\gamma_{A}$ work as the
“interpreter,” which transforms a valid configuration of $A$ into that of
$A^{\ast}$ under the assumption that the simulated agent executing $A^{\ast}$
stays at the same location as the simulator agent executing $A$. The
$\gamma$-configuration $\gamma(C)$ is the configuration of $A^{\ast}$ obtained
by interpretation. It may seem unusual that $\gamma(C)$ does not explicitly
depend on the value $m$ of the agent memory. However, it is indispensable that
algorithm $A$ stores the value of the agent memory of $A^{\ast}$ into the
storage of the current node of $A$ to simulate the behavior of the simulated
agent running $A^{\ast}$ by an oblivious agent. The simulation algorithm is
defined as follows:

######  Definition 4 (simulation of algorithm).

Let $A^{\ast}\in\mathcal{A}(1,\lambda^{\ast})$ be an algorithm. We consider
that _an algorithm $A\in\mathcal{A}(0,\lambda)$ simulates $A^{\ast}$ in $G$_,
if there exists a pair of mappings $\gamma=(\gamma_{M},\gamma_{A})$ of
Definition 3 that satisfy the following condition:

> Let $v$ be any node of $G$, $E(G,v,A)=(C_{t})_{t\geq 0}$, and
> $E(G,v,A^{\ast})=(C^{\ast}_{t})_{t\geq 0}$. There uniquely exists the
> monotonically increasing sequence of round numbers $T(0),T(1),T(2),\dots$
> such that $T(0)=0$ holds and $\gamma\left(C_{T(t)}\right)=C_{t}^{\ast}$
> holds for each $t\geq 0$. That is,
> $E\left(G,v,A^{\ast}\right)=\gamma\left(C_{T(0)}\right),\gamma\left(C_{T(1)}\right),\gamma\left(C_{T(2)}\right),\dots$
> holds.

Finally, we defined the round complexity of the simulation as follows:

######  Definition 5.

Let $A\in\mathcal{A}(0,\lambda)$ be the algorithm that simulates
$A^{\ast}\in\mathcal{A}(1,\lambda^{\ast})$. Then, the time required to
simulate round $t$ is defined as $T(t+1)-T(t)$. If $\max_{t\geq
0}\left(T(t+1)-T(t)\right)=\mathrm{poly}(n)$ holds for any $t\geq 0$, we
consider that _$A$ is a polynomial-time simulator of $A^{\ast}$ in $G$_.

##  3 Our Algorithm

We show a polynomial-time simulator $A\in\mathcal{A}(0,\lambda)$ that
simulates any one-bit agent algorithm
$A^{\ast}\in\mathcal{A}(1,\lambda^{\ast})$ in any 2-edge-connected graph $G$.
In the following argument, we denote the oblivious agent executing $A$ by the
symbol $a$ and the one-bit simulated agent executing $A^{\ast}$ by $a^{\ast}$.
We also denote
$A^{\ast}=\left(m^{\ast},M^{\ast},(M^{\prime})^{\ast},l^{\ast},\phi^{\ast}\right)$.
The storage size of algorithm $A$ is denoted by $\lambda$, which satisfies
$\lambda=\lambda^{\ast}+O(\log\Delta)$.

###  3.1 Mappings and Variables on Storage

We first introduce all the variables stored in the storage of each node in
Table 1.

Table 1: Variables used in our simulation algorithm. The initial location of $a$ (and $a^{\ast}$) is referred to as $v\in V$. Name |  Role
---|---
sloc |  The binary flag representing the current location of $a^{\ast}$, i.e., $sloc_{i}=1$ implies that the simulated agent $a^{\ast}$ is currently at node $i$. At any time, at most one node $i$ satisfies $sloc_{i}=1$. When $sloc_{i}=0$ holds for every node $i$, the algorithm is simulating the movement of $a^{\ast}$. Initially, $sloc_{v}=1$ for the initial location $v\in V$ of $a$ and $a^{\ast}$, and $sloc_{j}=0$ for any $j\neq v$.
smem |  The variable storing the current memory value of $a^{\ast}$ at the current node of $a^{\ast}$. It can store an arbitrary value at any other node.
smemupd |  The flag indicating the completion of the information transfer along the constructed ITC. At the beginning of the one-round simulation of $A^{\ast}$, the value is 0 for all nodes. When $a$ propagates a binary memory value $m^{\prime}$ of $a^{\ast}$ along the ITC, the node $i$ that has already received $m^{\prime}$ sets $smemupd_{i}=1$. The initial value is zero for all nodes.
spin |  The entry port number of $a^{\ast}$ at the current node. It can store an arbitrary value at any other node. Initially, an arbitrary value is stored.
spout |  The variable for storing the computed outgoing port number of $a^{\ast}$ at the current node. It can store an arbitrary value at any other node.
svars |  The storage for the simulated algorithm $A^{\ast}$. The initial value is the one specified by the algorithm $A^{\ast}$.
dfsstat |  The three-state variable used inside the DFS subroutine for constructing the ITC. If the agent $a$ does not execute the DFS subroutine, the value zero is stored at all nodes. The condition $dfsstat_{i}=1$ implies that the agent $a$ has visited $i$, but $i$ still has the ports not probed yet, and $dfsstat_{i}=2$ implies that all the ports of $i$ have been probed. The initial value is zero at all nodes.
par |  The variable storing the port number to the parent of the DFS tree. After the construction of an ITC, this variable represents the predecessor of the ITC. The initial value is arbitrary.
cld |  The counter indicating the ports that have been already probed: $cld_{i}=x$ implies that up to the $(x-1)$-th port of the node $i$ has been probed. After the construction of an ITC, this variable represents the successor in the ITC. The initial value is zero for all nodes.
sim |  The flag indicating the subtask in which the agent $a$ is engaged. If $sim_{i}=0$ holds for all nodes $i$, the agent is executing the DFS subroutine for constructing an ITC. Once an ITC is constructed, $sim_{i}=1$ holds if and only if $i$ is contained in the constructed ITC.
lastin/out |  In execution of the DFS subroutine, these variables manage the latest entry/outgoing port numbers at each node. The stored information is used for deleting the “garbage” information in the storage left by the DFS subtask.

Each variable is referred to with an additional subscript to clarify the node
that stores it. For example, $sloc_{i}$ denotes the variable sloc stored in
node $i$. For a tuple of variables $(X,Y)$ (where $X$ and $Y$ are the names of
some variables), we also use the notation $(X,Y)_{i}$ to represent
$(X_{i},Y_{i})$.

To formalize the correctness criteria of our simulation algorithm, we
introduce _legal configurations_ , defined as those satisfying
$(dfsstat,sim,smemupd)_{i}=(0,0,0)$ for all nodes $i\in V$, $sloc_{v}=1$ for
the current location $v$ of $a$, and $sloc_{i}=0$ for all other nodes $i\neq
v$. Our algorithm satisfies the condition that the sequence of all legal
configurations appearing during the execution of $A$ forms the simulated
execution of $A^{\ast}$. More precisely, let $E(G,v,A)=(C_{t})_{t\geq 0}$ and
$t_{0},t_{1},t_{2},\dots$ be the maximal sequence of the round numbers such
that $C_{t_{i}}$ is legal. Then, our simulation algorithm is correct with
respect to $T(i)=t_{i}$ and $\gamma=(\gamma_{M},\gamma_{A})$ such that
$\gamma_{M}(M_{i})=svars_{i}$ and $\gamma_{A}(M_{i})=(smem_{i},spin_{i})$
hold.

Let $\mathcal{C}$ be a set of all valid legal configurations. Our algorithm
starts from any configuration $C\in\mathcal{C}$ and guarantees that the legal
configuration $C^{\prime}\in\mathcal{C}$ satisfies
$\gamma(C)\xrightarrow{\phi^{\ast},G}\gamma(C^{\prime})$ without explicit
termination. Evidently, this algorithm provides simulated execution
$E(G,v,A^{\ast})$: Following the definition of the initial values specified in
Table 1, the initial configuration $C_{0}=C_{t_{0}}$ of the corresponding
execution $E(G,v,A)$ for any $v\in V$ is legal, and $\gamma(C_{0})$ becomes
the initial configuration of $E(G,v,A^{\ast})$. The algorithm then generates
the configuration $C_{t_{1}}$ such that
$\gamma(C_{t_{0}})\xrightarrow{\phi^{\ast},G}\gamma(C_{t_{1}})$ holds. The
algorithm immediately starts the next round of simulations, which generates
$C_{t_{2}}$ because $C_{t_{1}}$ is also legal. $A$ simulates the execution of
$E(G,v,A^{\ast})$ by repeating this process.

###  3.2 Overviews of Our Algorithm

First, we explain the high-level structure of the proposed algorithm. The
simulator algorithm consists of five subtasks: local computation, DFS, clean-
up, memory transfer, and move-and-reset phases. We denote by $s$ the node
where agent $a$ remains at the beginning of the one-round simulation. Because
the configuration at the beginning is legal, the simulated agent $a^{\ast}$
also stays at $s$ by definition. We present an outline of each phase as
follows:

Local Computation Phase:

This phase was executed once at the beginning of the one-round simulation of
$A^{\ast}$. The simulator agent locally simulates the local computation of
$A^{\ast}$ at node $s$ (i.e., the location of $a^{\ast}$) and then updates the
corresponding storage variables. After finishing the local computation phase,
agent $a$ immediately proceeds to the DFS phase.

DFS Phase:

Let $t$ be the node to which the simulated agent $a^{\ast}$ moves. Agent $a$
executes the DFS from $s$ with the first traversal edge $(s,t)$ until it
revisits $s$ (i.e., the node such that the variable sloc stores one). This
determines a cycle containing edge $(s,t)$, which becomes the ITC.

Clean-up Phase:

The agent repeats the same DFS traversal again from $s$ (with the first
traversal edge $(s,t)$) to revisit $s$ to reset the storage values left in the
DFS phase, except for the one necessary to recognize the ITC.

Memory Transfer Phase:

The agent circulates the ITC in the direction based on the memory value
$smem_{s}$ of simulated agent $a^{\ast}$.

Move-and-Reset Phase:

The agent moves simulated agent $a^{\ast}$ from $s$ to $t$ by setting
$sloc_{s}=0$ and $sloc_{t}=1$. It then resets the storage of all nodes in the
ITC to recover the legality of the configurations.

The agent determines the phase in which it is currently running based on the
storage values $(dfsstat,sim,\allowbreak smemupd,sloc,par)$ of the current
location and the current value of $p_{in}$. The details of this are explained
in the following section.

###  3.3 Details of Our Algorithm

In this subsection, we present the details of each phase. Pseudocodes are
presented in Algorithms 1, 2, 3, 4 and 5. Algorithm 1 presents the main part,
including the local computation phase. We denote the procedures of the five
phases above as LocalComp(), DFS(), CleanUp(), TransMem(), and MoveReset(),
respectively.

Algorithm 1 Main Part and LocalComp()

1:$p_{in}\leftarrow$ (entry port number)

2:$\Delta_{i}\leftarrow$ (the degree of the node $i$) $smemupd_{i}=1$

3:MoveReset() $dfsstat_{i}>0$ $sim_{i}=1\vee p_{in}=par_{i}\vee sloc_{i}=1$

4:CleanUp()

5:DFS() $sim_{i}=1$

6:TransMem() $sloc_{i}=1$ $\triangleright$ LocalComp()

7:$(spout,svars,smem)_{i}\leftarrow\phi^{\ast}(\Delta_{i},spin_{i},svars_{i},smem_{i})$

8:DFS()

The procedure LocalComp() is described in line 14 of Algorithm 1 (see the
comment in the pseudocode), and all other phases are separately described in
Algorithms 2, 3, 4 and 5. Hereinafter, we refer to a line $Y$ or lines $Y$-$Z$
of Algorithm $X$ as $(X,Y)$ or $(X,Y$-$Z)$. In all the pseudocodes, the
current location of agent $a$ is referred to as $i$. As in Section 3.2, we
denote the initial location and destination of $a^{\ast}$ in the simulated
round by $s$ and $t$, respectively.

#### Main part and local computation phase

The main part shown in Algorithm 1 calls for an appropriate procedure
according to the local storage value of node $i$. The local computation phase
is executed if $(dfsstat,sim,smemupd,\allowbreak sloc)_{i}=(0,0,0,1)$ holds.
As the initial configuration is legal, every node $i$ satisfies
$(dfsstat,sim,\allowbreak smemupd)_{i}=(0,0,0)$. We also have $sloc_{s}=1$ and
$sloc_{i}=0$ for all $i\neq s$ based on the constraint of the variable sloc.
According to the definition of sloc, the current location of $a^{\ast}$ is
also at $s$, and $smem_{s}$, $spin_{s}$, and $svars_{s}$ store the situation
of agent $a^{\ast}$ in the simulated execution. The simulator agent $a$
locally simulates the local computation of $A^{\ast}$ by $a^{\ast}$ at node
$s$ and stores the computed results in $spout_{s}$, $svars_{s}$, and
$smem_{s}$ (1,14). The DFS phase was invoked immediately after the local
computation phase (1,15).

#### DFS phase

We show the pseudocode for the DFS phase in Algorithm 2.

Algorithm 2 DFS()

1:$lastin_{i}\leftarrow p_{in}$ $sloc_{i}=1$

2:$(dfsstat,cld,lastout)_{i}\leftarrow(1,spout_{i},spout_{i})$ $dfsstat_{i}=0$
$\triangleright$ visiting by forward

3:$(dfsstat,par)_{i}\leftarrow(1,p_{in})$ $par_{i}=0$ $\triangleright$ skip
the parent port

4:$(cld,lastout)_{i}\leftarrow(1,1)$

5:$(cld,lastout)_{i}\leftarrow(0,0)$ $dfsstat_{i}=1\wedge p_{in}=cld_{i}$
$\triangleright$ visiting by backtrack $par_{i}=p_{in}+1$ $\triangleright$
skip the parent port

6:$cld_{i}\leftarrow p_{in}+2$

7:$cld_{i}\leftarrow p_{in}+1$ $cld_{i}<\Delta_{i}$ $\triangleright$ unprobed
ports exist

8:$lastout_{i}\leftarrow cld_{i}$ $\triangleright$ no unprobed port exists

9:$(lastout,dfsstat)_{i}\leftarrow(par_{i},2)$ $\triangleright$ invoking
backtrack

10:$lastout_{i}\leftarrow p_{in}$

11:Move to $\pi_{i}(lastout_{i})$

This phase is executed if one of the following conditions is satisfied:

  * •

$(dfsstat,sim,smemupd,sloc)_{i}=(0,0,0,0)$ or immediately after the local
computation phase (1,15),

  * •

$dfsstat_{i}>0$, $(sim,smemupd,sloc)_{i}=(0,0,0)$, and $p_{in}\neq par_{i}$
(1,9).

Intuitively, the first and second conditions are applied to the cases in which
the agent visits $i$ first and re-visits $i$. Lines (2,2-3) are for the
exceptional behavior of the first invocation of DFS() immediately after the
local computation phase. Then, the choice of the probed port must correspond
to edge $(s,t)$, that is, the port stored in $spout_{i}$. Note that, when the
agent visits node $i=s$ again, $dfsstat_{i}>0$ and $sloc_{i}=1$ are satisfied,
and (2,2-3) are not executed because the main routine invokes CleanUp() in
(1,7). Because the simulation starts from a legal configuration, the variables
$sim_{i}$, $smemupd_{i}$, and $sloc_{i}$ for any $i\neq s$ store 0 at the
beginning of the DFS phase and are not modified in the subroutine DFS().
Consequently, the DFS phase continues if the agent visits nodes other than
$s$. Throughout the DFS phase, the agent visiting node $i$ stores the entry
and outgoing port numbers in lastin and lastout, respectively. Line (2,1) is
for storing the entry port number. To store the outgoing port number, the
agent first writes the port number to which the agent will move into
$lastout_{i}$ (lines 3, 7, 9, 16, 18, and 20) and finally moves to the port
indicated by $lastout_{i}$ (2,21). The information of lastin and lastout is
used in procedure CleanUp(). During the DFS phase, the agent explored $G$
following the standard DFS. Specifically, it probes the ports of the visited
node individually in ascending order, which enables the agent to recognize the
ports already probed by storing only one port number. The latest probed port
number was stored in $cld_{i}$. When the agent returns to the current node $i$
through an edge with port number $cld_{i}$ by backtrack, $cld_{i}$ is
incremented. If $cld_{i}+1$ is the port indicating the parent of the DFS tree,
then it is skipped (2,6 and 2,11). 111Since the standard (centralized) DFS
always moves to a neighboring unvisited node, agent-based algorithms cannot
identify whether a neighbor is already visited. Hence, the agent must check
all the neighbors. Then, the following case can occur: the agent exits from
$i$ through port $p$, but the destination is already visited. Thus, it returns
immediately to $i$. In our algorithm, this case is treated as a backtrack. If
the value of $cld_{i}$ after the increment exceeds $\Delta_{i}-1$, the agent
has no neighbor of $i$ to be checked and thus performs the backtrack with
setting $dfsstat_{i}=2$ (2,18). When the agent visits $i$ more than once, the
variable $dfsstat_{i}$ stores a nonzero value at the second or later visit.
Then, the condition $(dfsstat,sim,smemupd)_{i}=(1,0,0)$ is satisfied, and the
entry port number is necessarily different from $par_{i}$ because, in such a
case, the agent traverses a non-DFS-tree edge or performs the backtrack.
Consequently, the agent can distinguish whether it visits $i$ by forward or
non-forward movement under conditions $dfsstat_{i}=1$ and $p_{in}\neq par_{i}$
(2,10).

#### Clean-up Phase

We show the pseudocode of the clean-up phase in Algorithm 3.

Algorithm 3 CleanUp()

$sim_{i}=0$$(dfsstat,sloc)_{i}=(1,1)$

1:$(par,dfsstat,sim)_{i}\leftarrow(p_{in},0,1)$

2:Move to $\pi_{i}(cld_{i})$

3:$sim_{i}\leftarrow 1$ $par_{i}=0$ $\triangleright$ skip the parent port

4:$cld_{i}\leftarrow 1$

5:$cld_{i}\leftarrow 0$ $(dfsstat,lastin,lastout)_{i}=(1,p_{in},cld_{i})$

6:$dfsstat_{i}\leftarrow 0$ $\triangleright$ initialization

7:Move to $\pi_{i}(cld_{i})$ $p_{in}=cld_{i}$ $\triangleright$ visiting by
backtrack $par_{i}=p_{in}+1$ $\triangleright$ skip the parent port

8:$cld_{i}\leftarrow cld_{i}+2$

9:$cld\leftarrow cld_{i}+1$ $dfsstat_{i}=1$
$(lastin,lastout)_{i}=(p_{in},cld_{i})$

10:$dfsstat_{i}\leftarrow 0$ $\triangleright$ initialization

11:Move to $\pi_{i}(cld_{i})$ $cld_{i}<\Delta_{i}$ $\triangleright$ unprobed
ports exist

12:Move to $\pi_{i}(cld_{i})$ $\triangleright$ no unprobed port exists
$(lastin,lastout)_{i}=(p_{in},par_{i})$

13:$(dfsstat,sim)_{i}\leftarrow(0,0)$ $\triangleright$ initialization

14:Move to $\pi_{i}(par_{i})$ $\triangleright$ invoking backtrack
$(lastin,lastout)_{i}=(p_{in},p_{in})$ $dfsstat_{i}=1$

15:$dfsstat_{i}\leftarrow 0$ $\triangleright$ initialization

16:$(dfsstat,sim)_{i}\leftarrow(0,0)$ $\triangleright$ initialization

17:Move to $\pi_{i}(p_{in})$

This phase is executed if $dfsstat_{i}>0$ holds, and either $sim_{i}=1$,
$p_{in}=par_{i}$, or $sloc_{i}=1$ is satisfied (1,5-6). This phase begins
immediately after the agent returns to $s$ during the DFS phase. At the
beginning of this phase, the set of nodes that satisfy $dfsstat=1$ forms an
ITC. It first updates $par_{i}(=par_{s})$ by $p_{in}$, resulting in consistent
orientation of the ITC by the variable par. In addition, the variable cld for
all nodes in the ITC presents the inverse orientation. The goal of this phase
is to reset all the nodes $i$ with $dfsstat_{i}>0$ by setting $dfsstat_{i}=0$
and marking the nodes $i$ in the ITC with $sim_{i}=1$. The agent in the clean-
up phase performs DFS up to the first revisit of $s$ similar to the DFS phase.
Every node $i$ visited in the clean-up phase must satisfy $dfsstat_{i}>0$
(every node $i$ satisfying $dfsstat_{i}>0$ is necessarily visited) because the
DFS traversal in this phase is the same as that in the DFS phase. The main
technical challenge is to make the agent distinguish between the DFS and
clean-up phases, particularly at the first visit of $i$. This issue was
resolved as follows: In the DFS phase, the agent never enters node $i$ with
$dfsstat_{i}>0$ (i.e., the second or later visit of $i$) through the edge with
port number $par_{i}$. Hence, if $p_{in}=par_{i}$ and $dfsstat_{i}>0$ holds in
the clean-up phase, agent $a$ correctly recognizes that it enters $i$ by the
forward movement of the DFS in the clean-up phase. The value update of
$sim_{i}$ from zero to one occurs when the agent visits $i$ first in the
clean-up phase (3,6), which enables the agent to distinguish between the
clean-up and DFS phases when revisiting $i$. During the execution, the agent
must initialize the information of the storages written in the DFS phase,
except for the information for the ITC (i.e., the information of $sim_{i}=1$
for $i$ in the ITC). However, resetting $dfsstat_{i}$ can result in the loss
of recognition in the current phase when the agent visits $i$ again in the
subsequent execution of the clean-up. To avoid this, the agent checks whether
the current visit of $i$ is the final one by comparing the number of entry and
outgoing ports to the values of $(lastin,lastout)_{i}$ left in the DFS phase.
One can show that the agent never visits $i$ again in the subsequent execution
of the clean-up phase if they are the same (formally proved as Claim 1).
Finally, when the agent returns to $s$, all unnecessary information is reset,
and the agent proceeds to the memory transfer phase under the condition
$(dfsstat,sim,smemupd)_{s}=(0,1,0)$ (1,10). It is noteworthy that $sim_{j}=1$
holds if and only if $j$ is contained in the constructed ITC.

#### Memory Transfer Phase

We show the pseudocode of the memory transfer phase in Algorithm 4.

Algorithm 4 TransMem()

$sloc_{i}=1$

1:$smemupd_{i}\leftarrow 1$ $smem_{i}=0$ $\triangleright$ transfer 0
($p_{in}=par_{i}$)

2:Move to $\pi_{i}(cld_{i})$ $\triangleright$ transfer 1 ($p_{in}=cld_{i}$)

3:Move to $\pi_{i}(par_{i})$ $\triangleright$ receive the transferred value

4:$smemupd_{i}\leftarrow 1$ $p_{in}=par_{i}$ $\triangleright$ transfer 0

5:$smem_{i}\leftarrow 0$

6:Move to $\pi_{i}(cld_{i})$ $\triangleright$ transfer 1

7:$smem_{i}\leftarrow 1$

8:Move to $\pi_{i}(par_{i})$

In this phase, the agent circulates ITC. Recall that node $i$ in the ITC is
identified by condition $sim_{i}=1$. The agent recognizes that the current
round is in the memory transfer phase if $(sim,dfsstat)_{i}=(1,0)$ holds
(1,10-11). It sets $smemupd_{i}=1$ and moves to one of $i$’s neighbors in the
ITC, specified by the value of $smem_{i}$. As stated above, the variables par
and cld at the nodes in the ITC present two opposite orientations of the ITC;
thus, we observe that agent $a$ transfers 0 if $p_{in}=par_{i}$ and 1
otherwise. The transferred value is written for all nodes in the ITC (4,10 and
4,13). If $smemupd_{i}=1$ at the visited node, the agent detects the
termination of circulating the ITC, which triggers the following move-and-
reset phase (1,3-4).

#### Move-and-Reset Phase

We show the pseudocode for the move-and-reset phases in Algorithm 5.

Algorithm 5 MoveReset()

$sloc_{i}=1$$\triangleright$ leave from $s$

1:$sloc_{i}\leftarrow 0$

2:Move to $\pi_{i}(spout_{i})$ $p_{in}=par_{i}$ $\triangleright$ reach to $t$

3:$(sloc,spin,sim,smemupd)_{i}\leftarrow(1,p_{in},0,0)$

4:Move to $\pi_{i}(par_{i})$ $\triangleright$ initialization

5:$(sim,smemupd)_{i}\leftarrow(0,0)$

6:Move to $\pi_{i}(par_{i})$

This phase is executed when $smemupd_{i}=1$ (1,3). First, agent $a$ sets
$sloc_{s}=0$ at node $s$, which implies that $a^{\ast}$ leaves $s$ and moves
to $\pi_{s}(spout_{s})=t$. At node $t$, the agent updates $sloc_{t}$ and
$spin_{t}$ by 1 and $p_{in}$, respectively (5,5). The one-round simulation of
$a^{\ast}$ finishes because $smem_{t}$ is already updated by the memory
transfer phase. The remaining task is to reset the expired information of
variables sim and smemupd left in the ITC. To reset this, the agent circulates
the ITC following the orientation by cld. The requirement for the orientation
is to make the agent distinguish the first movement (for updating sloc and
spin) from the following reset movement. Since the port number of the edge
$(s,t)$ at $t$ is $par_{t}$, if the agent visits $t$ with $p_{in}=par_{t}$, it
can recognize that the current round is for updating sloc and spin (5,4), in
contrast with the fact that $p_{in}=cld_{t}$ always holds in the reset
circulation. If $sloc_{i}=1$ holds in the reset circulation, this implies that
$i=t$, and $(dfsstat,sim,smemupd)_{i}=(0,0,0)$ also holds for all $i$. The
configuration becomes legal since all nodes not in the ITC have been reset
correctly in the clean-up phase.

###  3.4 Correctness

In this section, we prove that each procedure correctly executes the
corresponding phase and bound their running times. To prove this, we first
introduce the standard (centralized) DFS process under the following
conditions:

  1. 1.

Initially, the search head points at $s$ and moves to $t$ at the first
neighborhood search.

  2. 2.

When visiting $i\neq s$, the search head sequentially probes its neighbors
along the order of the corresponding port numberings.

  3. 3.

If the search head moves to a node $i$ already searched, it immediately goes
back to the previous node.

  4. 4.

The search process terminates when the search head reaches $s$ again.

where $s$ and $t$ denote the nodes defined in the previous section. We define
$V_{dfs}$ as the set of all nodes reached by the search head in this process
and $S=i_{0},i_{1},\dots i_{M}$ as the trajectory of the search head. Note
that, in this sequence, one node can appear more than once. In addition, for
node $s^{\prime}$ visited immediately before re-vising $s$, we define
$V_{ITC}$ as the set of nodes on the path from $s$ to $s^{\prime}$ in the DFS
tree. All $V_{dfs}$, $S$, and $V_{ITC}$ are uniquely determined only by nodes
$s$ and $t$, graph $G$, and its port numbering functions $\Pi$.

For any phase $X$, if the agent invokes the procedure corresponding to $X$ in
round $r$, we say that round $r$ is of phase $X$. To make it well-defined, we
slightly modified our algorithm by separating the round executing LocalComp()
and executing DFS(). That is, after the local computation phase, the agent
finishes the current round with no movement, and in the next round, it invokes
DFS(). Trivially, the correctness of the modified algorithm was lower than
that of the original algorithm. Let $r_{X}$ be the first round of phase $X$
during the execution. The _sub-execution_ of phase $X$ is defined as the
maximal period from $r_{X}$ in which every round is of phase $X$. For the
final round $r^{\prime}$ of the sub-execution of $X$, the configuration at the
beginning of round $r^{\prime}+1$ is called the _resultant configuration_ of
$X$.

A node $i$ is called _legal_ if it satisfies
$(dfsstat,sim,smemupd)_{i}=(0,0,0)$. First, we present the correctness
criteria for each phase.

######  Definition 6 (correctness of phases).

Each phase is called _correct_ if the sub-execution of the phase satisfies the
following condition:

Local Computation Phase

Starting from any valid legal configuration $C\in\mathcal{C}$, the resultant
configuration $C^{\prime}$ satisfies
$(spout,svars,smem)_{s}=\phi^{\ast}(\Delta_{l^{\ast}},p_{in}^{\ast},M^{\ast}_{l^{\ast}},m^{\ast})$
and $C^{\prime}\in\mathcal{C}$.

DFS Phase

Starting from the resultant configuration of any correct local computation
phase, the sub-execution reaches the resultant configuration satisfying as
follows:

  1. 1.

For any $u\in V$, $(sim,smemupd)_{u}=(0,0)$ holds.

  2. 2.

For any $u\in V$, $dfsstat_{u}=1$ holds if $u\in V_{ITC}$, $dfsstat_{u}=2$
holds if $u\in V_{dfs}\setminus V_{ITC}$, or $dfsstat_{u}=0$ holds otherwise.

  3. 3.

The variables $(spout,svars,smem)_{s}$ store the same values as the starting
configuration.

Clean-up Phase

Starting from the resultant configuration of any correct DFS phase, the sub-
execution reaches the resultant configuration satisfying as follows:

  1. 1.

For each $u\in V_{ITC}$, $(dfsstat,sim,smemupd)_{u}=(0,1,0)$ holds.

  2. 2.

For each $u\in V_{ITC}$, $\pi_{u}(par_{u})$ and $\pi_{u}(cld_{u})$ are also
contained in $V_{ITC}$, and letting $\pi_{u}(par_{u})=x$, $\pi_{x}(cld_{x})=u$
is satisfied.

  3. 3.

Any node $u\notin V_{ITC}$ is legal, and $(spout,svars,smem)_{s}$ store the
same values as the starting configuration.

Memory Transfer Phase

Starting from the resultant configuration of any correct clean-up phase, the
sub-execution reaches the resultant configuration satisfying as follows:

  1. 1.

For any $u\in V_{ITC}$, $(dfsstat,sim,smemupd)_{u}=(0,1,1)$ and
$smem_{u}=smem_{s}$ holds.

  2. 2.

Any node $w\notin V_{ITC}$ is legal, and $(spout,svars,smem)_{s}$ store the
same values as the starting configuration.

Move-and-Reset Phase

Starting from the resultant configuration of any correct memory transfer
phase, the sub-execution reaches the resultant configuration satisfying as
follows:

  1. 1.

Any node $i\in V$ is legal, and $sloc_{t}=1$ holds only for $t$.

  2. 2.

The variable $spin_{t}$ stores $\pi^{-1}_{t}(s)$ (i.e., the entry port number
of $a^{\ast}$).

  3. 3.

$smem_{t}=smem_{s}$.

It is easy to verify that the resultant configuration of the phase triggers
the subsequent phase. Hence, one can trivially deduce the correctness of our
algorithm based on the correctness of all phases. We focus on the correctness
of the remaining four phases because procedure LocalComp() is trivially
correct.

######  Lemma 1.

The DFS phase is correct.

###### Proof.

Procedure DFS() does not modify sim or smemupd. Because we assume that the
initial configuration is legal, this proof does not consider the conditions of
sim and smemupd, but focuses on the conditions of variable dfsstat. We first
show that the agent moves along the trajectory $i_{0},i_{1},\dots,i_{M}$
during the sub-execution of the DFS phase. If the procedure DFS() is invoked
in some rounds, it chooses the next visited node in the same way as the
centralized DFS explained above. Hence, it suffices to show that the DFS phase
continues until the round when the agent visits $s$. If $dfsstat_{i}=0$ holds,
procedure DFS() is necessarily executed (1,12 and 1,15). In addition, during
the DFS phase, $sim_{i}=0$ and $p_{in}\neq par_{i}$ hold for any $i\in V$ such
that $dfsstat_{i}>0$ because $dfsstat_{i}>0$ implies that $i$ is already
visited in the DFS phase. Thus, $par_{i}$ appropriately points to the parent
of $i$ in the DFS tree (evidently, the DFS search never visits node $i$ twice
through the edge from the parent). Thus, the sub-execution of the DFS phase
terminates if and only if $sloc_{i}=1$ and $dfsstat_{i}>0$ hold (1,5-7). When
agent $a$ revisits $s$, $dfsstat_{s}=1$ and $sloc_{s}=1$ hold. Hence, the DFS
phase continues until node $s$ has been revisited. We show that the resultant
configuration satisfies the condition of Definition 6. Let $s^{\prime}$ be the
last newly visited node in the DFS phase (i.e., the node immediately before
the revisit of $s$). Variable $dfsstat_{i}$ is set to 2 (and the agent
backtracks) if and only if all ports except that $par_{i}$ are probed.
According to the definition of $V_{ITC}$, the agent does not backtrack at any
node in $V_{ITC}$. That is, at any node $u\in V_{ITC}$, the agent does not
return to $u$ through the edge indicated by $cld_{u}$. This implies that
$dfsstat_{u}=1$ holds and the condition of Definition 6 is satisfied at any
$u\in V_{ITC}$. ∎

The proof of the clean-up phase contains a slight technical non-triviality in
the distinction of the DFS phase.

######  Lemma 2.

The clean-up phase is correct.

###### Proof.

As a proof of Lemma 1, we do not consider the condition of the variable
smemupd. In this phase, the agent traces the same route as in the DFS phase if
resetting dfsstat and sim at node $i$ occurs correctly at the last visit of
$i$. We prove this by inducing the indices of trajectory $i_{0},i_{1},\dots
i_{M}$. Let $c_{0},c_{1},\dots c_{M^{\prime}}$ be the trajectory of the agent
in the clean-up phase. We show that $c_{k}=i_{k}$ holds and $c_{k}$ satisfies
the conditions for executing the clean-up phase for any $k$. Because this
phase starts at node $s$, $c_{0}=i_{0}$ and the condition for executing the
clean-up phase is satisfied. Then, as the induction hypothesis, we assume that
$c_{k}=i_{k}$ is satisfied for each $k\in[0,j]$ and the condition for
executing the clean-up phase is satisfied at $c_{j}$. Because the method of
deciding the next probed neighbor is the same as the DFS phase,
$c_{j+1}=i_{j+1}$ is satisfied. Now, we have to show that the condition for
executing the clean-up phase is satisfied at $c_{j+1}$. If $c_{j+1}$ is
visited for the first time in this phase, $p_{in}=par_{c_{j+1}}$ holds, and
the agent sets $sim_{c_{j+1}}=1$. Otherwise, the proof is performed if
$sim_{c_{j+1}}=1$ holds; that is, $c_{j+1}$ is not reset up to round $j$. As
we have already shown in Lemma 1 that $i_{0},i_{1},\dots,i_{M}$ is also the
trajectory of the agent in the DFS phase, the agent stores the entry/outgoing
port numbers in the variables lastin and lastout of node $i_{k}$ in the $k$-th
round of the DFS phase. Let $L_{k}$ be a pair of values stored in
$(lastin,lastout)_{i_{k}}$ when visiting $i_{k}$. Then, we have the following
claim.

######  Claim 1.

For any $k^{\prime},k\in[0,M]$, $L_{k^{\prime}}\neq L_{k}$ holds, if
$i_{k}=i_{k^{\prime}}$ holds.

###### Proof.

Assume $k^{\prime}<k$ without loss of generality, and let $u=i_{k^{\prime}}$
for short. We denote the values of lastin and lastout in $L_{x}$ as
$lastin(x)$ and $lastout(x)$ respectively. First, consider the case in which
round $k^{\prime}$ is the first visit of $u$ in the DFS process. Subsequently,
$lastin(k^{\prime})=par_{u}$ holds. Because the agent visits $u$ from its
parent only at the first visit, we have $lastin(k)\neq par_{u}$, and thus the
claim holds. Next, consider the case in which round $k^{\prime}$ is not the
first visit of $u$. If $lastin(k^{\prime})=lastin(k)$ holds, then the agent
visits $u$ in rounds $k^{\prime}$ and $k$ through the same edge $(w,u)$. There
exist two scenarios in which the agent traverses edge $(w,u)$ in the second or
later visit of $u$: In the first scenario, the agent moves forward from $u$ to
$w$, but $w$ has already been visited and thus returns to $u$ by backtracking.
Second, the agent moves forward from $w$ to $u$. These two are all possible
scenarios, and thus they occur at rounds $k^{\prime}-1$ and $k-1$,
respectively. While the agent leaves from $u$ with the port necessarily
different from $\pi^{-1}_{u}(w)$ in the first scenario, it leaves with the
edge to $w$ in the second scenario (because the next movement is backtracked
to $w$). That is, the two scenarios choose different numbers of outgoing ports
to leave $u$. Thus, $lastout(k^{\prime})\neq lastout(k)$ holds. The claim
holds. ∎

Suppose that, for contradiction, $c_{j+1}$ is reset in round $k\leq j$.
Because $c_{j+1}=i_{j+1}$ holds, round $k$ is not the last visit of
$c_{k}=c_{j+1}$. Let $c_{k^{\prime}}$ be the last visit of
$c_{j+1}(k^{\prime}>k)$, and Claim 1 implies that $L_{k^{\prime}}\neq L_{k}$.
This contradicts the assumption that $c_{j+1}$ is reset to the round $k$.
Consequently, $c_{j+1}$ is not reset to round $j$ and it can be concluded that
the trace of the agent is the same as that of the DFS phase. In addition, it
has been proven that reset at node $i$ occurs at the last visit of $i$. From
these two facts, it is easy to verify that the resultant configuration
satisfies the condition of Definition 6. The lemma is proved. ∎

The correctness of the memory transfer and the move-and-reset phases is
relatively straightforward.

######  Lemma 3.

The memory transfer phase is correct.

###### Proof.

Under the condition of the initial configuration, the nodes $i$ with
$sim_{i}=1$ induce ITC, and variables par and cld provide two opposite
orientations. Hence, evidently, the agent correctly circulates the ITC in the
memory transfer phase and terminates at the initial position $s$ (note that,
at the beginning of the phase, the agent sets $smemupd_{s}=1$; thus, when it
returns to $s$, the memory transfer phase necessarily terminates). Assuming
that variables par and cld provide two opposite orientations if the agent
leaves $s$ through port $par_{s}$, it enters the next node $x$ through port
$cld_{x}$ and vice versa. This observation implies that the simulated memory
value $smem_{s}$ is correctly transferred to all nodes in the ITC, and the
condition of the resultant configuration in Definition 6 is satisfied. ∎

######  Lemma 4.

The move-and-reset phase is correct.

###### Proof.

Under the condition of the initial configuration, all nodes not in $V_{ITC}$
have already been legal (i.e., $(dfsstat,sim,smemupd)=(0,0,0)$). As explained
in Section 3.3, the agent correctly circulates the ITC along the orientation
using cld and resets sim and smemupd. Because dfsstat is already zero, we can
conclude that the resulting configuration is legal. The remaining issue is to
show that it is the configuration interpreted as that for $A^{\ast}$ after a
one-round simulation. It has already been shown that the memory value is
transferred correctly and $svars_{s}$ is updated correctly in the local
computation phase. In addition, the agent updates $spin_{t}$ by $p_{in}$ at
the first movement from $s$ to $t$ in the move-and-reset phase; that is,
$spin_{t}$ stores the port number of edge $(s,t)$. Because $a^{\ast}$ moves
from $s$ to $t$ in this round, $spin_{t}$ is equal to the entry port number of
$a^{\ast}$ in the next simulated round. ∎

By combining all of the lemmas above, we obtain the main theorem.

######  Theorem 1.

Algorithm $A$ shown in Algorithm 1 correctly simulates $A^{\ast}$ in any
2-edge-connected graph $G$. The round complexity of the algorithm to simulate
one round of $A^{\ast}$ is $O(n^{2})$. The required storage size is
$O(\lambda^{\ast}+\log\Delta)$ bits per node.

###### Proof.

The correctness clearly follows Definition 6, and all phases are correct. To
limit time complexity, we bound the running time of each phase. The first two
phases (i.e., DFS and clean-up) depend on the running time of DFS. To execute
DFS for the graph such that the number of nodes and edges are $\left\lvert
V\right\rvert$ and $\left\lvert E\right\rvert$, respectively, it needs
$O(\left\lvert E\right\rvert)=O(n^{2})$ rounds. The running time of the
remaining two phases was bounded by $O\left(\left\lvert
V_{ITC}\right\rvert\right)=O(n)$ rounds. Hence, the total running time (per
round of simulation) is $O(n^{2})$.

The storage size consumes $\lambda^{\ast}$ bits for svars, which corresponds
to the storage of $A^{\ast}$. The sizes of the other variables are bounded by
$O(\log\Delta)$. The storage size was $O(\lambda^{\ast}+\log\Delta)$ bits per
node. ∎

##  4 Conclusion

In this study, we demonstrated the equivalence of the computational power of a
single oblivious agent and a single one-bit memory agent in a 2-edge-connected
graph with $O(\log\Delta)$-bit storage by presenting the algorithm
$A\in\mathcal{A}(0,\lambda)$ that simulates any
$A^{\ast}\in\mathcal{A}(1,\lambda^{\ast})$ on 2-edge-connected graphs with
$\lambda=\lambda^{\ast}+O(\log\Delta)$. The time overhead of our simulation
algorithm was $O(n^{2})$ per round. That is, if the original algorithm
$A^{\ast}$ runs in polynomial time, then our simulator also works in
polynomial time. Finally, we conclude this study by explaining the open
problem. The primary open problem deduced from our results is whether an
oblivious agent can simulate any one-bit agent on 2-edge-connected graphs
under the assumption that only $O(1)$-bit storage per node is available. As a
weaker form of this problem, 2-edge-connected graphs with $O(1)$-bit storage
per node can be also explored.

## Acknowledgement

This study was initiated by the discussion with Prof. Shantanu Das when he
visited the third author (Taisuke Izumi) in 2018. We greately appreciate his
valuable comments at the discussion.

## References

  * [1] Reuven Cohen, Pierre Fraigniaud, David Ilcinkas, Amos Korman, and David Peleg.  Label-guided graph exploration by a finite automaton.  ACM Trans. Algorithms, 4(4):42:1–42:18, 2008.
  * [2] Ajoy Kumar Datta, Anissa Lamani, Lawrence L. Larmore, and Franck Petit.  Enabling ring exploration with myopic oblivious robots.  In 2015 IEEE International Parallel and Distributed Processing Symposium Workshop, IPDPS 2015, Hyderabad, India, May 25-29, 2015, pages 490–499. IEEE Computer Society, 2015.
  * [3] Yoann Dieudonné, Shlomi Dolev, Franck Petit, and Michael Segal.  Explicit communication among stigmergic robots.  Int. J. Found. Comput. Sci., 30(2):315–332, 2019.
  * [4] Yann Disser, Jan Hackfeld, and Max Klimm.  Undirected graph exploration with $\circleddash$(log log _n_) pebbles.  In Robert Krauthgamer, editor, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, pages 25–39. SIAM, 2016.
  * [5] Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, and David Peleg.  Graph exploration by a finite automaton.  Theor. Comput. Sci., 345(2-3):331–344, 2005.
  * [6] Taisuke Izumi, Kazuki Kakizawa, Yuya Kawabata, Naoki Kitamura, and Toshimitsu Masuzawa.  Deciding a graph property by a single mobile agent: One-bit memory suffices, 2022.
  * [7] Sayaka Kamei.  Autonomous distributed systems of myopic mobile robots with lights.  In ICDCN ’21: International Conference on Distributed Computing and Networking, Virtual Event, Nara, Japan, January 5-8, 2021, page 5. ACM, 2021.
  * [8] Sayaka Kamei, Anissa Lamani, Fukuhito Ooshita, Sébastien Tixeuil, and Koichi Wada.  Gathering on rings for myopic asynchronous robots with lights.  In Pascal Felber, Roy Friedman, Seth Gilbert, and Avery Miller, editors, 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17-19, 2019, Neuchâtel, Switzerland, volume 153 of LIPIcs, pages 27:1–27:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
  * [9] Fukuhito Ooshita and Sébastien Tixeuil.  Ring exploration with myopic luminous robots.  Inf. Comput., 285(Part):104702, 2022.
  * [10] Omer Reingold.  Undirected connectivity in log-space.  J. ACM, 55(4):17:1–17:24, 2008.
  * [11] Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa.  A single agent exploration in unknown undirected graphs with whiteboards.  IEICE Trans. Fundam. Electron. Commun. Comput. Sci., 98-A(10):2117–2128, 2015.