# Black Hole Search in Dynamic Cactus

###### Abstract

We study the problem of black hole search node by a set of mobile agents of a
class of dynamic networks, namely constantly connected dynamic cactus graphs.
The black hole node is a vertex of the graph that eliminates visiting agents
without any trace. This problem has already been studied where the underlying
graph is a dynamic ring [di2021black].

In this paper, we consider the same problem, and we suppose that the
underlying graph is a dynamic cactus graph (a connected graph in which any two
simple cycles have at most one vertex in common) of $n$ vertices with $\alpha$
many 1-degree nodes. We propose a lower bound $\alpha+3$ on the number of
agents for a single dynamic edge, an algorithm allowing the agents to explore
and finds the black hole node using $\alpha+5$ agents with $O(\alpha n)$
moves. For the general case, in the presence of $k$ dynamic edges, we propose
a lower bound $\alpha+2k+1$ on the number of agents, an algorithm allowing the
agents to explore these dynamic graphs and find the black hole node using
$2\alpha+4k+6$ agents with $O((\alpha+k)n^{2})$ moves by agents.

###### Keywords:

Black hole search, Dynamic cactus graphDynamic networks Time-varying graphs
Mobile agents computing

##  1 Introduction

We study the black hole search problem in a dynamic cactus graph, where edges
can appear and disappear over time so the underlying graph remains connected.
More precisely, the network is a synchronous cactus graph where one of the
vertices (or nodes) is a malicious node that eliminates visiting agents
without any trace of their existence upon arrival on such nodes; that node is
termed as Black Hole [dobrev2006searching]. A group of mobile agents solves
the problem, all of them executing the same algorithm synchronously, and they
are initially located at a safe node. The aim is to successfully locate the
position of the Black Hole at a minimum time, with at least one agent
surviving.

The problem of black hole search (BHS) is essentially a special case of the
exploration problem. Exploration problem is one of the fundamental problems in
this domain of distributed computing by mobile entities (robots or agents).
The aim of this problem is that each node of the underlying topology must be
visited one or more mobile entities, also termed as mobile agents. Shanon
[shannon1993presentation], first designed an algorithm designed for graph
exploration. Many variations of this problem can be found in [das2013mobile],
in which nodes in a network with distinct identity or an anonymous network
have been studied. Further variations such as exploration with termination
[panaite1999exploring] and perpetual exploration [darwich2022perpetual] have
also been explained. There are innumerable many assumptions on which this
problem has been extensively studied such as, different models of
communication (i.e., whiteboard, pebble, face-to-face, etc.) on the degree of
synchrony (i.e., asynchronous, semi-synchronous and fully-synchronous), and
further on the amount of internal as well as external memory (refer the papers
[albers2002exploring, cohen2008label, chalopin2010network,
fraigniaud2005graph, fraigniaud2008impact]). All of the above variations have
a common assumption, the underlying network is static, i.e., the set of edges
remain constant over time in the underlying graph. These graphs fail to
address the challenges arising from highly dynamic networks.

Related Work. Recently, the research focus has been converted from static
graphs to highly dynamic graphs, also termed as time varying graphs (TVG).
This concept of TVG, is first formally defined by Casteigts et al.
[casteigts2012time]. The problem of exploration in dynamic graphs by a mobile
agent has been studied in different underlying topologies such as ring
[di2020distributed, gotoh2020dynamic], tori [gotoh2021exploration], cactuses
[ilcinkas2021exploration] and in general graph [gotoh2021exploratio]. In
[gotoh2021exploratio], gave a bound of $2\eta(\mathcal{G})+1$ on the number of
agents in a dynamic arbitrary graph $\mathcal{G}$ in both fully-synchronous
(FSYNC) and semi-synchronous (SSYNC) scheduler, where $\eta(\mathcal{G})$ is
the number of transient edges in the graph, which are also termed as
evanescence of the graph. Moreover, they gave a bound of $2l+1$ agents under
SSYNC scheduler and $2l$ agents under FSYNC scheduler in a dynamic graph
$\mathcal{G}$ which is $k$-bounded 1-interval graph. Further they gave bounds
of $2l$ and $2l-1$ on the number of agents under SSYNC and FSYNC scheduler,
respectively in the same graph $\mathcal{G}$ which is $k$-bounded 1-interval
graph. The only thing they assumed that regardless of an edge is present or
missing at a particular moment, the node has the indication of all the port
numbers. This assumption does not exist in our case.

The black hole search problem is well-studied in varying underlying topologies
such as rings, grids, torus, etc. This problem has been first introduced by
Dobrev et al. [dobrev2006searching], where they solved this problem in static
arbitrary topology by providing tight bounds on the number of agents as well
as the providing cost of a size-optimal solution. After this seminal paper,
there has been a plethora of work done in this domain under different graph
classes such as trees [czyzowicz2007searching], rings [dobrev2007locating],
tori [ilcinkas2021exploration] and in graphs of arbitrary topology
[czyzowicz2006complexity, dobrev2006searching]. Now, in all the above
literature, the study has been performed when the underlying graph is static.

While most of the study has been done on static networks, very few literature
is known of BHS specially in highly dynamic graphs. Flocchini et al.
[flocchini2012searching] studied the black hole search problem in a different
class of dynamic graphs, defined as periodically varying graphs, they showed
the minimum number agents required to solve this problem is $\gamma+1$, where
$\gamma$ is the minimum number of carrier stops at black holes. Di Luna et al.
[di2021black], studied the BHS problem in highly dynamic network, which is
essentially a dynamic ring. They studied this problem under various
communication model (i.e., face-to-face, vision, pebble, whiteboard, etc.) and
they gave tight bounds on the number of agents needed in order to find the
black hole. In this paper, we aim to solve the similar problem, but in our
case we have considered the underlying topology is a highly dynamic cactus
graph.

Contributions. Our contributions to this paper are the following. We study the
black hole search problem for a dynamic cactus graph with mobile agents.

  * •

We gave a lower bound of $\alpha+3$ agents that are required to locate the
black hole in a dynamic cactus graph $\mathcal{G}$ having $\alpha$ many
1-degree nodes in which at most one edge is dynamic (i.e., the edge can
disappear and appear in a round).

  * •

We propose an algorithm that successfully finds the black hole position using
$\alpha+5$ agents with $\mathcal{O}(\alpha n^{2})$ moves in presence of one
dynamic edge.

  * •

We give a lower bound of $\alpha+2k+1$ agents that are required to locate the
black hole position in a dynamic cactus graph $\mathcal{G}$ having $\alpha$
many 1-degree nodes in which at most $k$ edges are dynamic.

  * •

We propose an algorithm that requires $2\alpha+4k+6$ agents to successfully
locate the black hole position in $\mathcal{G}$ with
$\mathcal{O}((\alpha+k)n^{2})$ moves in presence of at most $k$ dynamic edges.

##  2 Model and Preliminaries

Graph: The dynamic cactus graph is modeled as a time varying graph (TVG):
$\mathcal{G}$ = $G_{0},G_{1},\cdots,G_{r},\cdots$, where
$G_{r}=(V,\mathcal{E}_{r})$ and $|V|=n$ is the cactus graph corresponding to
the present edges at round $r$, also termed as footprint of $\mathcal{G}$. The
TVG $\mathcal{G}$ can have at most $k$ edge (where $k\geq 1$) can be missing
at any round such that $\forall G_{i}\in\mathcal{G}$, $G_{i}$ is connected,
which in turn implies that the edge removed must be part of some cycle. The
vertices in $\mathcal{G}$ are anonymous, i.e., they are unlabeled. An edge
$e=(u,v)$ must have two port numbers, one adjacent to $u$ and the other
adjacent to $v$. $\Delta$ is denoted as the maximum degree of the graph. A
node $u\in V$ with $deg(u)$ is connected with its neighbors at round $r$,
$\mathcal{E}_{r}(u)=\\{u_{0},u_{1},\cdots,u_{\deg(u)-1}\\}$ via port numbers
$\rho_{0},\rho_{1},\cdots,\rho_{deg(u)-1}$, which are labeled in ascending
order along a counter-clockwise direction. The network $\mathcal{G}$ contains
a malicious node also termed as black hole, which eliminates any incoming
agent without leaving any trace of its existence.

Agent: An agent visiting a node can read the port numbers, while entering and
leaving a port. The set of mobile agents $A$ = $\\{a_{1},\cdots,a_{k}\\}$ are
initially co-located at a safe node (also termed as home base) in
$\mathcal{G}$. Agents have distinct and visible IDs, i.e., if more than one
agent are present together at the same node, then each can see the other’s ID.
Among these set of agents, one agent is elected as a $LEADER$. The $LEADER$
has the ability to give instructions to other agents. The agents move from one
node to another using the port numbers. They cannot distinguish between a
missing edge and an edge which does not exit, this is because the agents have
no knowledge about the degree of a node. More precisely, it cannot detect the
difference between a node with 1-degree (pendant vertex) and a node with
degree two having one edge missing. Further, the underlying topology or the
graph $\mathcal{G}$ is unknown to the agents. We say that a graph
$\mathcal{G}$ is explored if all the nodes in $\mathcal{G}$ is visited at
least once by one or more agents.

The agents operate in synchronous rounds, where each agent gets activated in
each round. After activation, the agent at a node $v$ at some round $r$, takes
local snapshot of $v$ that contains the set $\mathcal{E}_{r}(v)$ and the set
of agents present at this round at the node $v$. The agents also communicate
among themselves either implicitly or explicitly. Now, based on the internal
memory, local snapshot and local communication, the agent decides what step to
take. The step performed by an agent is divided in to communication step and a
move step. In the communication step, the agents can communicate among
themselves only when they are at the same node (also termed as Face to Face
($F2F$) model). They communicate among themselves in order to exchange their
gathered information. In the move step, the agent either decides to move along
an edge $e=(v,v^{\prime})\in\mathcal{E}_{r}(v)$, which will take it to the
node $v^{\prime}$ at the round $r+1$ or stay at the current node. An agent can
traverse an edge in one round. The goal of the team of agents is to search for
the location of the black hole. Hence, this problem is popularly termed as
Black Hole Search (BHS) problem. The problem definition as follows:

######  Definition 1 (Black Hole Search Problem)

Given a time varying cactus graph $\mathcal{G}$, a set of agents and an
arbitrary black hole node in $\mathcal{G}$, the objective of the problem is to
ensure at least one agent remains alive and knows the position of the black
hole node.

Here, we discuss some basic definitions about the model and about the basic
protocols and principles which will be used in our algorithm.

######  Definition 2 (Dynamic Graphs [ilcinkas2021exploration])

A dynamic graph $\mathcal{G}=(V,\mathcal{E})$, is a graph with $|V|$ static
vertices and $\mathcal{E}$ is a mapping which maps $i\in\mathbb{Z}^{+}$ to the
set of undirected edges $\mathcal{E}_{i}$ on V.

######  Definition 3 (Underlying Graph [ilcinkas2021exploration])

A dynamic graph $\mathcal{G}=(V,\mathcal{E})$, with its static version
$G=(V,\bigcup_{i=0}^{\infty}\mathcal{E}_{i})$ is called the underlying graph
of $\mathcal{G}$.

######  Definition 4 (Cactus Graph)

A cactus is a connected graph in which any two simple cycles have at most one
common vertex.

######  Definition 5 (Dynamic Cactus Graph)

A dynamic cactus graph is a time varying cactus graph, in which at most $k$
edges are missing at any round, such that the underlying graph is connected.

It is to be noted that the missing edge must be part of some cycle to keep the
dynamic cactus graph connected.

######  Definition 6 (Stuck Point)

Given a dynamic cactus graph $\mathcal{G}$, an agent cannot distinguish
between the node with 1-degree and a node which was initially of degree two,
but transformed in to a node with 1-degree due to a disappearing edge. These
kinds of nodes are defined as stuck points in $\mathcal{G}$.

One cactus graph is illustrated in Fig. 1, where nodes $v_{7}$, $v_{14}$ and
$v_{15}$ are all stuck points. Now, whenever the edge $(v_{7},v_{8})$
reappears, then $v_{7}$ ceases to be a stuck point.

Figure 1: A port labeled Cactus Graph in which $\rho_{0}$, $\rho_{1}$ and
$\rho_{2}$ are the port numbers corresponding to the node $v_{8}$, which are
depicted for other nodes as well

The next definition directly follows from the paper [gotoh2021exploratio].

######  Definition 7 ($k$-Bounded 1-interval connected)

A dynamic cactus graph $\mathcal{G}$ is 1-interval connected (or it is
connected at any round) if $\forall G_{i}\in\mathcal{G}$, $G_{i}$ is
connected. Moreover, $\mathcal{G}$ is said to be $k$-bounded 1-interval
connected if at any round at most $k$ many edges can be removed such that the
underlying footprint of $\mathcal{G}$ remains connected.

Cautious Walk. This is a movement strategy for agents in a network with black
hole, which ensures that more than one agent does not enter the black hole
from the same edge. The idea of this walk is as follows. Two agents $a_{1}$
and $a_{2}$ are initially located at a node $u$, then an agent $a_{1}$ decides
to move to an unexplored node $v$ along the edge $(u,v)$. If the node $v$ is
safe, then $a_{1}$ returns back to $u$ and together $a_{1}$ and $a_{2}$
travels to the node $v$.

Let two agents $a_{1}$ and $a_{2}$ are located initially at the home base $h$
(refer Fig. 1). In the next round, $a_{1}$, moves along port $\rho_{0}$ to the
node $v_{1}$. Since, $v_{1}$ is a safe node, the agent $a_{1}$ upon visiting
this $v_{1}$, returns back to $h$ in the next round. Subsequently, both the
agents move together along the port $\rho_{0}$, towards the node $v_{1}$ and
this process continues. But if $a_{1}$ and $a_{2}$ both are located at
$v_{17}$ and $a_{1}$ moves along port $\rho_{0}$ keeping $a_{2}$ at $v_{17}$.
In the next round $a_{1}$ cannot return at $v_{17}$ because $a_{1}$ is
eliminated by the black hole at $v_{19}$. As a consequence $a_{2}$ finding the
edge present, and $a_{2}$ not returning back at $v_{17}$ in the next round,
declares $v_{19}$ as the black hole.

Pendulum Walk [di2021black]. An agent $a_{1}$ travels to and fro movement and
reports to another agent $a_{2}$ (may be referred as a “witness” agent). More
precisely, let us consider that two agents $a_{1}$ and $a_{2}$ are located at
a node $u$. Now, $a_{1}$ decides to move one hop along the edge $(u,v)$ and
reaches a node $v$. If the node $v$ is safe, then it returns back to $u$.
Again, $a_{1}$ decides to move two hops along the edge $(u,v)$ and $(v,w)$
reaches to $w$. If $w$ is safe, then it returns back to $u$ via $v$. In
general, $a_{1}$ in each movement increments the hop count by one, reaches a
node along the path $P=u\rightarrow v\rightarrow w\longrightarrow\cdots$. If
that node is safe, it returns back to $u$.

##  3 Lower Bound on Agents to find Black Hole

Initially, we study the lower bound on the number of agents required to solve
the BHS problem when at most one edge can be disappeared or appeared in a
round. Then we generalize this idea for the case, when at most $k$ edges can
be disappeared or appeared in a round such that the underlying footprint
remains connected. We therefore give some impossibility results in the next
section on the number of agents.

###### Lemma 1

Given a dynamic cactus graph $\mathcal{G}$ with at most one missing edge in a
round and $t$ many agents. Let $\mathcal{G}$ has $\alpha$ many 1-degree nodes,
where $\alpha<t$. In order to explore $\mathcal{G}$, at least one agent must
be placed at each of these $\alpha$ many nodes.

###### Proof

We prove the above claim by contradiction. Let $\mathcal{H}$ be any algorithm
executing on a graph $\mathcal{G}$ (in Fig. 2), in which there is a single
agent $a_{j}$ (say) which tries to explore two 1-degree nodes. When the agent
at round $r$, reaches a node of 1-degree and a node which is of 1-degree due
to a missing edge, cannot distinguish between these two variety of nodes. So
we have further possibilities:

  * •

Possibility-1: The agent $a_{j}$ assigned to explore two nodes, both of them
are nodes of 1-degree due to a missing edge at that round (refer the node
$v_{5}$ when the agent visits it at round $r$ and the node $v_{9}$ when the
agent visits it at round $r^{\prime}$ in Fig. 2).

  * •

Possibility-2: The agent $a_{j}$ assigned to explore two nodes, one among them
is originally of 1-degree whereas the other node is a node of 1-degree due to
a missing edge at that round, when the agent visits that node (refer the nodes
$v_{p_{1}}$ and $v_{5}$ in Fig. 2).

  * •

Possibility-3: The agent $a_{j}$ assigned to explore the two nodes are
originally of 1-degree (refer the nodes $v_{p_{1}}$ and $v_{p_{2}}$ in Fig.
2).

In case of possibility-1, there are two nodes of 1-degree to be explored and a
single agent $a_{j}$ is assigned to visit these nodes. Moreover, as these two
nodes are part of a missing edge, the adversary can alter their positions at
any certain round. It means that when the agent reaches one of such node
$v_{5}$ (refer Fig. 2) at round $r$, it has no knowledge about the fact that
whether this node is originally of degree two and moreover, it is part of a
bigger cycle. Now, if this agent remains at this location, then the other node
remain unexplored. So, when the agent $a_{j}$ leaves the node $v_{5}$ and
traverses for the other node, adversary revives the edge $(v_{5},v_{6})$ and
removes $(v_{6},v_{9})$ at round $r^{\prime}$ (refer Fig. 2). So, the agent
enters a another node of 1-degree due to a missing edge, i.e., the node
$v_{9}$ in Fig. 2. Hence, the adversary successfully restricts the agent to
visit the nodes $\\{v_{6},v_{7},v_{8}\\}$. This implies that, following the
algorithm $\mathcal{H}$ there is a certain part of $\mathcal{G}$ which remain
unexplored. Hence this gives the contradiction to the fact that a single agent
without staying at one of these 1-degree nodes tries to explore another
1-degree node.

The other two cases are duplicate version of possibility-1. The reason follows
from the inability of the agents to distinguish between an 1-degree node due
to a missing edge and an original 1-degree node. Hence, the other two
possibilities are similar for the agents as it cannot distinguish between
these two set of nodes. So, in each case at least one agent remains stationary
at each of the 1-degree nodes of $\mathcal{G}$. ∎

###### Corollary 1

In worst case, a team of agents need to explore the whole graph in order to
locate the exact position of the black hole.

######  Lemma 2 ([di2021black])

Let $\mathcal{G}$ be a dynamic ring of size $n>3$. Let the agents have the
knowledge that the black hole is located in any one among these three
consecutive nodes $H=\\{v_{1},v_{2},v_{3}\\}$. In this case, it is not
possible to locate the black hole position with two agents.

###### Remark 1

Any dynamic cactus graph, with $\alpha$ many 1-degree nodes and one missing
edge has at most $\alpha+2$ many stuck points.

Figure 2: Representing a dynamic cactus graph with $\alpha$ many one degree
nodes, which depicts the removal of edge $(v_{5},v_{6})$ at round $r$ and the
edge $(v_{6},v_{9})$ at round $r^{\prime}$, the underlying graph remains
connected

######  Theorem 3.1 (Impossibility for a single dynamic edge)

Let $\mathcal{G}$ be a dynamic cactus graph of size $n\geq 3$, where at most
one edge can be missing at any round such that the underlying graph is
connected. Let us consider that there are $\alpha$ many 1-degree nodes in
$\mathcal{G}$, then it is not possible to locate the position of the black
hole with at most $\alpha+2$ agents.

###### Proof

Consider the graph $\mathcal{G}$ (refer Fig. 2), with $\alpha$ many degree 1
nodes and at most one missing edge at any round. We prove the theorem by
contradiction. Let there exists an algorithm $\mathcal{H}$, that uses
$\alpha+2$ agents, in order to successfully locate the position of black hole
in $\mathcal{G}$. Now, by corollary 1 any algorithm $\mathcal{H}$ in worst
case requires to explore the whole graph in order to locate the black hole
position. Moreover, as $\mathcal{G}$ has $\alpha$ many degree 1 nodes, by
lemma 1 each of these nodes must be occupied by at least one agent. Now, as
the black hole is positioned inside a cycle of $\mathcal{G}$. According to
lemma 2, it is not possible for the remaining two agents to successfully
locate the black hole position. Hence, this leads to a contradiction, that
algorithm $\mathcal{H}$ using $\alpha+2$ agents successfully finds the black
hole in $\mathcal{G}$. ∎

######  Corollary 2 (Lower bound for a single dynamic edge)

In order to successfully locate the black hole in a dynamic cactus graph with
$\alpha$ 1-degree vertex and at most one missing edge, any algorithm must
require at least $\alpha+3$ agents.

###### Remark 2

In a dynamic cactus graph $\mathcal{G}$ with $\alpha$ many 1-degree vertices
and $k$ edge deletions has at most $\alpha+2k$ stuck points.

######  Theorem 3.2 (Impossibility for $k$ dynamic edges)

Let $\mathcal{G}$ be a dynamic cactus graph of size $n\geq 3$, with $\alpha$
many 1-degree vertices and at most $k$ many edge deletions at any round $r$,
it is not possible to correctly locate the black hole position with at most
$\alpha+2k$ agents.

###### Proof

Let $\mathcal{G}$ be a graph with $\alpha$ many 1-degree vertices and can have
at most $k$ many missing edges, such that the underlying footprint is
connected. Let $\mathcal{H}$ be any algorithm that successfully finds the
location of black hole with $\alpha+2l$ agents. We prove the claim by
induction.

Base Case: When $l=1$, the claim holds by theorem 3.1. Hence, base case is
true.

Induction Hypothesis: Let the claim holds when number of edge deleted at any
round of $\mathcal{G}$ is at most $k-1$, i.e., the algorithm $\mathcal{H}$
cannot find the location of the black hole with $\alpha+2(k-1)$ agents, with
$\mathcal{G}$ containing $\alpha$ many 1-degree nodes and at most $k-1$ edge
deletions.

Inductive Step: When there are $k$ missing edges and $\alpha$ degree 1 nodes,
we prove the above claim as follows. Continuing from the induction hypothesis,
$\alpha+2(k-1)$ agents cannot find the black hole position executing algorithm
$\mathcal{H}$. There are $\alpha+2(k-1)$ nodes corresponding to $\alpha$
1-degree nodes and $k-1$ missing edges. Now each of these nodes are treated as
1-degree nodes by the agent, as they cannot distinguish between these
variation. So, by lemma 1 at least one agent must be present at each of these
$\alpha+2(k-1)$ many nodes. Now, moreover there is another edge missing, which
is part of some other cycle of $\mathcal{G}$. Now, the remaining two agents
cannot explore this cycle and find the black hole position, which follows from
the lemma 2. Hence, following the algorithm $\mathcal{H}$, $\alpha+2k$ agents
cannot successfully locate the black hole position in a graph $\mathcal{G}$
with $\alpha$ 1-degree node and at most $k$ missing edge. ∎

######  Corollary 3 (Lower bound for $k$ dynamic edges)

In order to successfully locate the black hole in a dynamic cactus graph with
$\alpha$ 1-degree vertices and at most $k$ missing edges at any round $r$, any
algorithm must require at least $\alpha+2k+1$ agents.

###### Observation 3.3

Anonymous co-located agents with $F2F$ communication cannot solve BHS in a
static cactus graph, regardless of their number.

The observation readily follows from the result stated in [di2021black], where
it is explained in case of static rings.

The next observation, gives a brief idea about the movement of the agents on a
cycle inside a dynamic cactus graph. It states that, when a single agent is
trying to explore any unexplored cycle, the adversary has the power to confine
the agent on any single edge of the cycle. Moreover, in case of multiple
agents trying to explore a cycle inside a cactus graph, but their movement is
along one direction. In that case as well, the adversary has the power to
prevent the team of agents to visit further unexplored nodes.

###### Observation 3.4

Given a dynamic cactus graph $\mathcal{G}$, and a cut $U$ (with $|U|>1$) of
its footprint connected by edges $e_{1}$ in the clockwise direction and
$e_{2}$ in the counter clockwise direction to the nodes in $V\char 92\relax
U$. If we assume that all the agents at round $r$ are at $U$, and there is no
agent which tries to cross to $V\char 92\relax U$ along $e_{1}$ and an agent
tries to cross along $e_{2}$, then the adversary may prevent agents to visit
nodes outside $U$.

This observation follows from the observation 1 of [di2021black].

###### Observation 3.5

In a cactus graph, consider a node $h$ and a set of three consecutive nodes
$\\{v_{0},v_{1},v_{2}\\}$. We observe that any path from $h$ to $v_{1}$ must
either traverse through $v_{0}$ or through $v_{2}$.

The above observation follows from the structural property of a cactus graph.

##  4 Black Hole Search in Dynamic Cactus

In this section, we first present an algorithm to find the black hole in the
presence of at most one dynamic edge, and then we present an algorithm to find
the black hole in the presence of at most $k$ dynamic edges. The number of
agents required to find the black hole is presented for each algorithm.

###  4.1 Black Hole Search in Presence of Single Dynamic Edge

Here we present an algorithm $\mathcal{A}$ for the agents to locate the black
hole position in the presence of at most one dynamic edge in a cactus graph.

Figure 3: State diagram of the BHS algorithm $\mathcal{A}$

We create a state diagram as shown in Fig. 3, which represents all possible
states of the nodes and the corresponding state transition (directed) paths
that the team of agents can travel starting from the particular node $home$ in
a dynamic cactus graph $\mathcal{G}$. The states in this diagram represent the
possible state of a node, when an agent visits it traversing from $home$. The
state SafeVertex in Fig. 3, represents the collection of all safe nodes in
$\mathcal{G}$ which are vacant when an agent visits them, whereas the state
SafeVertexwithAgent depicts the set of safe nodes in $\mathcal{G}$ occupied by
at least one agent. The state 1-degreeVertex represents two sets of nodes.
Firstly, the nodes of 1-degree (i.e., the pendant vertices). Secondly, the
degree two nodes, which gets transformed to 1-degree at the moment an agent
visits that node, due to an edge deletion. The state 1-degreeVertexwithAgent
represents a set of 1-degree vertex vertices which are occupied by any other
agent. Lastly, the state BlackHole represents the node consisting of the black
hole in $\mathcal{G}$. The dotted directed edges originating from the states
1-degreeVertex and 1-degreeVertexwithAgent, denotes the revival of a missing
edge from the nodes in $\mathcal{G}$ which are assumed to be 1-degree vertices
by the agent. A directed edge $(u,v)$ labeled by E (Exploring Port) represents
that the agent from $u$-th state travels to $v$-th state via an explored port,
whereas the edge labeled by T (Tracing Agent) denotes a port which the agent
is exploring for the first time. Finally, the edge labeled by $E|T$ (denoted
as $E|T$ in Fig. 3), represents that the agent can travel from $u$-th state to
$v$-th state along an explored as well as along an edge which is being
explored for the first time. Observe, that there are no outgoing edges labeled
as T or $E|T$ from the states 1-degreeVertexwithAgent and SafeVertexwithAgent.
This is because an agent finding another agent, backtracks along and does not
proceed further to explore unexplored ports. This idea is a part of an
algorithm strategy $\mathcal{A}$ which explained in the next section as high
level idea.

####  4.1.1 High Level Idea:

Let a team of $m$ agents $a_{1},\cdots,a_{m}$ are initially located at a safe
node $h$, also termed as home base. Without loss of generality, we assume the
agent $a_{m}$, elected as $LEADER$. The $LEADER$ remains stationary at $h$.

The task of the $LEADER$ can be divided in to four categories:

  * •

It instructs other agents, either to explore or to trace.

  * •

It maintains the sequence of ports $port[a_{i}]$, an ordered set of port
numbers traversed by $a_{i}$ during each movement.

  * •

It maintains the parameter $length[a_{i}]$, which stores the length of the
path traversed by $a_{i}$, where $i\in\\{1,2,\cdots,m-1\\}$.

  * •

It terminates the algorithm whenever it knows the black hole position, either
by itself or with the help of other agents.

An agent performs two kinds of movement such as explore and trace which are
explained as follows:

  * •

In explore it performs a pendulum walk to explore vertices.

  * •

In trace it traces the path of an agent which is exploring.

Figure 4: A dynamic cactus graph

The movement of explore is explained with the help of an example. Let us
consider four agents $a_{1}$, $a_{2}$, $a_{3}$ and $LEADER$ are initially
located at $home$ (refer Fig. 4). The agents $a_{2}$ and $a_{3}$ have
performed explore from $home$ and reached the vertices $v_{4}$ and $v_{7}$, by
following the paths $home\longrightarrow v_{1}\longrightarrow
v_{2}\longrightarrow v_{3}\longrightarrow v_{4}$ and $home\longrightarrow
v_{1}\longrightarrow v_{2}\longrightarrow v_{3}\longrightarrow
v_{6}\longrightarrow v_{7}$, respectively. As $a_{1}$ is instructed to
explore. It carries $port[a_{2}]$ and $port[a_{3}]$ obtained from the
$LEADER$, where $port[a_{2}]=\\{\rho_{0},\rho_{0},\rho_{0},\rho_{1}\\}$ and
$port[a_{3}]=\\{\rho_{0},\rho_{0},\rho_{0},\rho_{3},\rho_{1}\\}$. Whenever,
$a_{1}$ reaches a node to explore, it first checks $port[a_{i}]$
($i\in\\{2,3\\})$ to identify the set of unexplored ports and then decides its
next movement. More, precisely when $a_{1}$ reaches $v_{3}$ during
exploration, it finds $\rho_{1}$ and $\rho_{3}$ are already explored by its
predecessors, so $\rho_{2}$ is the only unexplored port. Hence, it follows
$\rho_{2}$ and reaches $v_{5}$. On the other hand, if $a_{1}$ is instructed to
trace $a_{2}$, then it carries only $port[a_{2}]$ and follows the sequence of
ports in $port[a_{2}]$.

When two agents meet at a node, they exchange their obtained information.

An agent fails to report back to the $LEADER$ for the following reasons:

  * •

When it either sees an unoccupied node having 1-degree while exploring.

  * •

When it enters the black hole node.

  * •

When it gets stuck by a disappearing edge while coming back to the $LEADER$.

  * •

When it finds a disappearing edge while tracing.

The basic idea of the algorithm is as follows:

  1. 1.

In the first round, two explorers $a_{1}$ and $a_{2}$ start a pendulum walk
from home using the ports $\rho_{0}$ and $\rho_{1}$. As per pendulum walk both
of them report back to $LEADER$. Moreover, during each subsequent exploration
they choose the lowest available port.

  2. 2.

The $LEADER$ updates $length[a_{i}]=length[a_{i}]+1$ and $port[a_{i}]$
whenever agent $a_{i}$ returns, where $i\in\\{1,2\\}$.

  3. 3.

If any one of the agents ($a_{1}$, say) fails to report, then $LEADER$ after
waiting $2(length[a_{1}]+1)$ rounds, instructs agent $a_{3}$ at home to trace
the path follow the path of $a_{1}$ by setting $length[a_{3}]=length[a_{1}]$
and $port[a_{3}]=port[a_{1}]$.

    1. (a)

If $a_{3}$ does not find $a_{1}$ at its last reported node, whereas the edge
corresponding to the lowest port number is not missing, then after waiting for
one round, if $a_{1}$ does not return back, then $a_{3}$ confirms that $a_{1}$
has entered the black hole, and starts backtracking towards $LEADER$.

      1. i.

If $a_{3}$ fails to return at $home$ within $2~{}length[a_{3}]+1$ rounds, then
the $LEADER$ directs agent $a_{4}$, to start explore along $\rho_{1}$ if there
are two ports or along $\rho_{2}$ if there are more than two ports from
$home$.

      2. ii.

Otherwise, $a_{3}$ returns $home$ and $LEADER$ obtains the black hole position
and terminates the algorithm.

    2. (b)

If $a_{3}$ finds $a_{1}$ at the last reported node and fails to return $home$
within $2~{}length[a_{3}]+1$ rounds, then the $LEADER$, directs agent $a_{4}$,
to start explore along $\rho_{1}$ if there are two ports or along $\rho_{2}$
if there are more than two ports from $home$.

    3. (c)

Otherwise, $a_{3}$ finds $a_{1}$ at the last reported node then $a_{1}$
settles at that node and $a_{3}$ returns $home$.

    4. (d)

  4. 4.

If there is no other agent is present at $home$ except $LEADER$, then the
$LEADER$ waits for
$\underset{i\in\\{1,2,\cdots,\alpha+4\\}}{max}{\\{2(length[a_{i}]+1)\\}}$
rounds,

    1. (a)

If an agent instructed to explore reports within this waiting period, then the
agent continues to explore.

    2. (b)

If an agent instructed to trace returns within this period then $LEADER$
instructs it to explore.

    3. (c)

Otherwise, if no agent returns then the $LEADER$ concludes that the black hole
position is the node which is to be explored by the last reported agent and
terminates the algorithm.

####  4.1.2 Detailed Description:

Our algorithm $\mathcal{A}$ works with $\alpha+5$ agents. Let the agent
$a_{\alpha+5}$ is elected as $LEADER$. All the agents are initially co-located
at the $home$.

To begin with, two agents $a_{1}$ and $a_{2}$ are instructed to explore along
the ports $\rho_{0}$ and $\rho_{1}$. Each agent performs a depth-first search
(DFS) traversal at each iteration of explore. The $LEADER$ also instructs
$a_{1}$ and $a_{2}$ to choose the lowest available port while it explores.
Whenever $a_{i}$ returns to $home$, the $LEADER$ updates $port[a_{i}]$ and
$length[a_{i}]$, where $i\in\\{1,2\\}$. While each $a_{i}$ performs its
movement, we have the following possibilities:

  * •

Possibility - 1: An agent (say, $a_{1}$ without loss of generality) enters the
black hole node.

  * •

Possibility - 2: $a_{1}$ enters a node which is originally of 1-degree.

  * •

Possibility - 3: $a_{1}$ enters a node inside a cycle, which is initially of
degree two, but one of its edges is missing.

  * •

Possibility - 4: $a_{1}$ explores a new node which is a part of cycle, and
while it backtracks to convey this information to the $LEADER$, one of the
edges of the cycle along its path goes missing.

In each of the above case, the agent $a_{1}$ fails to report. Meanwhile, the
$LEADER$ after waiting for $2(length[a_{1}]+1)$ rounds, instructs an agent
$a_{3}$ to trace $a_{1}$, while assigning $port[a_{3}]=port[a_{1}]$ and
$length[a_{3}]=length[a_{1}]$. As $a_{3}$ traces we encounter the following
cases:

  * •

Case-1: $a_{3}$ reaches the node of $a_{1}$ and finds that it is stuck (refer
to the case, when $a_{1}$ is stuck at the nodes $v_{7}$ or $v_{15}$ in Fig. 1,
as these nodes are of 1-degree at the moment $a_{1}$ reaches them).

  * •

Case-2: $a_{3}$ does not find $a_{1}$ at the last reported node, whereas the
edge corresponding to the lowest available port is missing (refer the
instance, where $a_{1}$ has reached the node $v_{8}$, as $a_{3}$ reaches
$v_{7}$ it does not find $a_{1}$ whereas the edge $(v_{7},v_{8})$ is missing
in Fig. 1).

  * •

Case-3: $a_{3}$ cannot find $a_{1}$ at the last reported node, but the edge
corresponding to the lowest available port exists (refer to the case when
$a_{1}$ has entered BH, whereas $a_{3}$ has reached the node $v_{17}$).

We deal with each of the above cases. In the first case, $a_{3}$ tries to
report back to $home$ whereas $a_{1}$ remains stationary until an edge
reappears corresponding to the lowest available port. While returning back,
the agent $a_{3}$ may face further possibilities:

  * •

Sub Case-1: While returning, $a_{3}$ gets stuck by a disappearing edge along
its path towards $home$, this implies the edge for which $a_{1}$ is
stationary, reappears. So, $a_{1}$ after finding that its current node is not
of 1-degree, also tries to return to $home$ and gets stuck with $a_{3}$ while
backtracking. The $LEADER$ in the meantime, after waiting $2(length[a_{3}])$
rounds, understands the fact that $a_{1}$ and $a_{3}$ a stuck at the same
cycle. So, it decides to instruct another agent at $home$ ($a_{4}$, say), to
explore while choosing the second lowest available port. As, $a_{4}$ carries
$port[a_{i}]$ (where $i\in\\{1,2,3\\}$). So, whenever there is a choice of non
visited ports $\rho_{0},\rho_{1},\cdots,\rho_{deg(v)-1}$ at a node $v$, the
agent $a_{4}$ will choose the second lowest among them. Otherwise, if there
are no non visited ports available, then $a_{4}$ tries to choose a port not
traversed by either $a_{1}$ or $a_{3}$. The reason behind this is explained
with an example. Consider the scenario, where both $a_{1}$ and $a_{3}$ entered
the cycle $v_{4}\longrightarrow v_{5}\longrightarrow v_{6}\longrightarrow
v_{9}\longrightarrow v_{4}$ in Fig. 2. Let, that the lowest port at $v_{4}$
takes an agent to $v_{9}$. Initially, when $a_{1}$ reached the node $v_{9}$,
it encounters an 1-degree node, and hence $a_{1}$ got stuck. So, $a_{3}$,
which is being tasked to trace $a_{1}$, finds $a_{1}$ at $v_{9}$. So, when it
tries to report this information to the $LEADER$, the adversary reappears
$(v_{6},v_{9})$ whereas deletes $(v_{4},v_{9})$. While they are both stuck at
$v_{9}$, $a_{4}$ reaches the node $v_{4}$. At this situation if $a_{4}$ again
chooses the lowest available port, then the adversary creates a situation
where $a_{1}$, $a_{3}$ and $a_{4}$ are all stuck at the same node. So, to
handle this scenario, the agent $a_{4}$ is instructed to choose the second
lowest available port, which in turn takes it to $v_{6}$ from the alternate
path. This ensures either of these agents can return $home$ unobstructed.

When $a_{4}$ finds $a_{3}$, it discovers that both $a_{1}$ and $a_{3}$ are
stuck. So, to ensure that not more than one agent is stuck at a stuck point,
$a_{4}$ carries $a_{3}$ while reporting back to $home$, whereas $a_{1}$
remains stationary until the edge reappears. As, $a_{3}$ and $a_{4}$ is
backtracking, we may have more scenarios::

    * –

Scenario-1: The adversary again plays a game to disappears an edge along the
path of $a_{3}$ and $a_{4}$, whereas reappearing the edge adjacent to the node
of $a_{1}$. This ensures $a_{1}$ to return $home$, whereas $a_{3}$
encountering stuck point with $a_{4}$, leaves $a_{4}$ and tries to backtrack
towards $home$. In the meantime if $a_{4}$ fails to report back to $LEADER$.
Then $a_{5}$ is instructed to trace $a_{4}$ and report back to $LEADER$.

    * –

Scenario-2: The agents $a_{3}$ and $a_{4}$ successfully reach $home$, whereas
$a_{1}$ remains stuck.

  * •

Sub Case-2: $a_{3}$ returns back to $home$, the $LEADER$ sets
$length[a_{3}]=0$ and instructs $a_{3}$ to perform explore.

In the second case (i.e., case-2), there are two possibilities:

  * •

$a_{1}$ has entered black hole while the adjacent edge is missing.

  * •

$a_{1}$ is stuck at the other end of the missing edge (refer the case in Fig.
1 when $a_{1}$ is at $v_{8}$ which is a safe node, but the edge
$(v_{7},v_{8})$ is missing).

In each of the above possibilities, after reappearing the edge, $a_{3}$ waits
for one round to see the return of $a_{1}$. If $a_{1}$ does not return, then
$a_{3}$ concludes that $a_{1}$ has entered black hole and tries to report this
information to the $LEADER$.

Otherwise, if $a_{1}$ returns back, then both $a_{1}$ and $a_{3}$ unites
together and tries to return $home$. While returning it may face the similar
scenarios as explained in sub case-1. If they successfully returns back then
$a_{1}$ remains at $home$ until it receives further instruction from $LEADER$,
whereas $a_{3}$ is instructed to explore.

In the third case (i.e., in case-3), the agent $a_{3}$ waits for one round at
the node last reported by $a_{1}$. If $a_{1}$ does not return back, then
$a_{3}$ concludes that $a_{1}$ has entered black hole and tries to report back
to $home$.

Similar situation occurs with the agent $a_{2}$ as well, which is performing
explore concurrently.

Following this strategy, if black hole location is not detected at any round
$r^{\prime\prime}<r^{\prime}$. Then there exists a round $r^{\prime}$ at which
all the $\alpha+2$ stuck points will be occupied by $\alpha+2$ agents, whereas
the two remaining agents except the $LEADER$ will be able to explore the
unexplored graph and if none of the agent reports to the $LEADER$ within
$\underset{i\in\\{1,2,\cdots,\alpha+4\\}}{max}{\\{2(length[a_{i}]+1)\\}}$
rounds. The $LEADER$ concludes that the black hole position is the node to be
explored by the last reported agent and terminates the algorithm.

####  4.1.3 Correctness and Complexity:

In this section, we prove the correctness of our algorithm $\mathcal{A}$ and
further give the minimum number of agents required to successfully execute the
algorithm $\mathcal{A}$.

###### Lemma 3

The algorithm $\mathcal{A}$ ensures that at most one agent is occupied by a
stuck point.

[Adri: Need to manage the placement of lemma’s and prove this above lemma]

###### Lemma 4

A team of agents executing the algorithm $\mathcal{A}$, ensures that at least
one agent is performing its movement until any agent concludes the black hole
node.

###### Proof

According to the algorithm $\mathcal{A}$, if any agent fails to report then
another agent is instructed to either trace or explore. In worst case, a
situation may arise where all the $\alpha+2$ stuck points are occupied by an
agent each, by lemma 3. Since, we have at least $\alpha+4$ agents except the
$LEADER$, to locate the black hole. So, the remaining two agents will be able
to perform its usual instruction until it detects the black hole node or
enters the black hole node. ∎

###### Lemma 5

Any agent which enters the black hole following the algorithm $\mathcal{A}$ is
instructed to explore.

###### Lemma 6

When there is no agent left at home base except $LEADER$. Moreover, none of
the agent reports back while the $LEADER$ waits
$\underset{i\in\\{1,2,\cdots,\alpha+4\\}}{max}{\\{2(length[a_{i}]+1)\\}}$
rounds. The $LEADER$ concludes that the black hole position is the node with
respect to the edge along which $a_{j}$ has traveled from the last reported
node, where $a_{j}$ is the last reported agent to the $LEADER$.

###### Proof

Given, $a_{j}$ is the last agent to report to the $LEADER$. Let us consider
$a_{i}$ be an agent, which has reported immediately before $a_{j}$. So, now we
have the further possibilities:

  * •

$a_{j}$ gets the instruction from the $LEADER$ due to $a_{i}$. In this case,
$a_{j}$ starts to trace for $a_{i}$ and we have further cases:

    * –

$a_{i}$ has entered the black hole and when $a_{j}$ reaches the last reported
node of $a_{i}$, it finds that $a_{i}$ is not present at that node, and the
edge corresponding to the lowest port number is also present. So by algorithm
$\mathcal{A}$, $a_{j}$ after waiting for one round concludes that $a_{i}$ has
entered black hole. Now, when $a_{j}$ tries to provide this information to the
$LEADER$, it gets stuck by a missing edge.

    * –

$a_{j}$ went to the last reported node of $a_{i}$, finds that the edge
corresponding to the lowest port is missing, it waits at that node until the
edge reappears.

    * –

$a_{j}$ while traversing to the last reported node of $a_{i}$, finds a missing
edge and waits for the edge to reappear.

All the above cases, explain the fact that $a_{j}$ is stuck while reporting
back to $LEADER$ or while tracing for the agent $a_{i}$. Since, there are at
most $\alpha+2$ stuck points whereas $\alpha+4$ agents are active in
$\mathcal{G}$, but no agent reported back to the $LEADER$ within
$\underset{i\in\\{1,2,\cdots,\alpha+4\\}}{max}{\\{2(length[a_{i}]+1)\\}}$
rounds of waiting. This means that each of them are in one of the possible
states, either stuck due to a missing edge or stuck while reporting back to
the $LEADER$ or entered black hole. In either case, $a_{i}$ must have entered
black hole otherwise there must be at least one agent other than $a_{i}$ and
$a_{j}$ which should have reported back within this waiting period. Moreover,
the maximum distance the agent $a_{j}$ must have traveled before reporting is
$length[a_{i}]$ as it acts as a tracer. This concludes, the statement that if
$a_{j}$ is instructed to explore rather than to trace, then it should have
also chosen the same port as $a_{i}$.

  * •

$a_{j}$ is instructed to explore, while exploring it stopped reporting back to
the $LEADER$ for
$\underset{i\in\\{1,2,\cdots,\alpha+3\\}}{max}{\\{2(length[a_{i}]+1)\\}}$
rounds, whereas no other agent also reported back within this round. In this
scenario, the only two possibilities except the fact $a_{j}$ entered black
hole are as follows: $a_{j}$ is stuck at some vertex and it cannot report back
to the $LEADER$ and $a_{j}$ found some stuck vertex while continuing to
explore and remained at that vertex. Now, if either of these cases arise, then
some other agent must have reported back to the $LEADER$ as there are
$\alpha+4$ active agents whereas $\alpha+2$ stuck points. So, the only
possible scenario is that $a_{j}$ has entered black hole. Now, $a_{j}$
traveled along the either the lowest or the second lowest available port which
is known to the $LEADER$ as it instructs the movement of each agent. This
concludes the statement.

∎

###### Lemma 7

The algorithm $\mathcal{A}$, ensures that at most two agents enter the black
hole node.

The theorem gives the bound on the number of agents required by the algorithm
$\mathcal{A}$, in order successfully locate the black hole position.

###### Theorem 4.1

Given a dynamic cactus $\mathcal{G}$, with $\alpha$ pendant vertices and at
most one missing edge at any round. The algorithm $\mathcal{A}$, requires at
least $\alpha+5$ agents in order to successfully locate the position of the
black hole.

###### Proof

We prove the above claim by contradiction. Let, there are $\alpha+4$ agents to
execute the algorithm $\mathcal{A}$ on $\mathcal{G}$. According to the
algorithm, $LEADER$ remains stationary at the $home$, and declares the
location of the black hole in two scenarios:

  * •

Scenario-1: any one among the $\alpha+3$ agents except the $LEADER$, reports
the black hole position to the $LEADER$.

  * •

Scenario-2: $LEADER$ unanimously declares the black hole position.

In case of scenario-1, there is nothing to prove, whereas scenario-2 occurs
when no agent reports to the $LEADER$ for a certain number of rounds (refer
the bound on lemma 6). Let $a_{i}$, $a_{j}$ and $a_{k}$ be the last three
agents located at $home$ along with $LEADER$. Assume, that the remaining
$\alpha$ agents are stuck at the $\alpha$ 1-degree vertices no agent has
entered black hole yet. Suppose, the agent $a_{i}$ is instructed to explore,
and while exploring it enters black hole and fails to report. Now, according
to algorithm $\mathcal{A}$, $a_{j}$ is triggered to trace for $a_{i}$. While
tracing it understands that $a_{i}$ has entered black hole and concludes the
black hole position. Now, while reporting back this information, it gets stuck
by a missing edge. In the meantime, the $LEADER$ understands that $a_{i}$ and
$a_{j}$ are stuck at the same cycle and initiates $a_{k}$ to explore along the
path not traversed by $a_{i}$ and $a_{k}$. Now, in the worst case, it may
happen that $a_{k}$ gets stuck by the other end of this missing edge, whereas
the $LEADER$ after waiting for the
$\underset{i\in\\{1,2,\cdots,\alpha+4\\}}{max}{\\{2(length[a_{i}]+1)\\}}$
rounds, concludes that $a_{k}$ has entered black hole, which is a
contradiction. ∎

[Adri: Rethink the above proof]

###### Theorem 4.2

Given a dynamic cactus graph $\mathcal{G}$ with $\alpha$ many 1-degree node
and at most one disappearing edge at any round, the algorithm $\mathcal{A}$
with $\alpha+4$ agents finds the location of the black hole with
$\mathcal{O}(\alpha n^{2})$ moves.

###### Proof

Given a $n$ node dynamic cactus graph $\mathcal{G}$, where the maximum number
of edges is $\lfloor\frac{3(n-1)}{2}\rfloor$. Now following the algorithm
$\mathcal{A}$, each agent traverses an edge at most $3(n-1)$ many times. This
implies, the total number of moves performed by each agent is at most
$3(n-1)\lfloor\frac{3(n-1)}{2}\rfloor$. Since, $\alpha+4$ agents are executing
the algorithm $\mathcal{A}$, hence the total number of moves performed by the
team of agents in order to successfully locate the black hole position is at
most $3(n-1)(\alpha+4)\lfloor\frac{3(n-1)}{2}\rfloor$, i.e.,
$\mathcal{O}(\alpha n^{2})$. ∎

###  4.2 Black Hole Search in Presence of Multiple Dynamic Edges

In this section, we deal with the case when the graph $\mathcal{G}$ is
$k$-bounded 1-interval connected, i.e., at most $k$ edges ($k>1$) can
disappear and appear at any round. Let us consider that there are $\beta$ many
simple cycles in $\mathcal{G}$, then $k$ can be at most $\beta$. We design an
algorithm $\mathcal{B}$ for the agents to locate the black hole position in
the presence of at most $k$ dynamic edge in a cactus graph.

We create another state diagram in Fig. 5, where we represent all the possible
states of the nodes and the corresponding state transitions (directed) paths
that a team of agents can travel starting from the home base $h$ in a dynamic
cactus graph $\mathcal{G}$. This state diagram follows from the one defined in
section 4.1, the only difference is that there are some additional states
defined in this state diagram, which are used in order to deal with more than
one edge disappearing and reappearing case. The additional states are defined
as follows. The state $SN_{BH}$ in Fig. 5 represents a set of vacant safe
nodes adjacent to the black hole node. Moreover, the state $SN_{BH}|A$
represents the set of nodes, which are adjacent to the black hole node and
they are occupied by at least one agent, i.e., whenever an agent visits this
set of nodes, it finds some other agent is already present at these nodes. In
the next section we discuss the high level idea of the algorithm
$\mathcal{B}$.

Figure 5: State diagram of the BHS algorithm $\mathcal{B}$

####  4.2.1 High Level Idea:

Let a team of $m$ agents $a_{1},\cdots,a_{m}$ are initially located at $h$.
Without loss of generality, consider $a_{m}$ as the $LEADER$. The task of the
$LEADER$ is same as described in section 4.1.1. The $LEADER$ always tries to
activate a pair of agents until and unless an even number of agents are
located at $h$. Moreover, when two agents meet they exchange their gathered
information. A pair of agents $a_{i}$ and $a_{i+1}$ (where
$i\in\\{1,2,\cdots,m-1\\}$) fails to report in any one of the following cases:

  * •

If both of them while performing a composite walk enters an 1-degree node
which is not occupied by any other agent.

  * •

When $a_{i}$ enters the black hole, whereas $a_{i+1}$ knowing the black hole
position stays at its current node with that information.

  * •

When both of them gets stuck by a disappearing edge while reporting back to
the $LEADER$.

  * •

When they find a disappearing edge while tracing the path of some other pair
of agents.

An activated pair of agents performs two kinds of movement:

  * •

Explore: In this movement, the pair of agents perform a composite walk to
explore the unexplored nodes. This composite walk is an accumulation of both
cautious and pendulum walk, where an agent $a_{1}$ first explores a node, then
it goes back to report that information to the other agent $a_{2}$ and then
they together go to the $LEADER$ in order to transmit this gained information
and then come back to this newly explored node.

  * •

Trace: This phenomenon occurs when a pair of agents fails to report to the
$LEADER$. In this scenario, the $LEADER$ activates another pair of agents,
where they together follow the path traversed by the other pair of agents and
report back its existence to the $LEADER$.

The high level idea of the algorithm is defined as follows:

  1. 1.

At any round $r$ of the algorithm, let a pair of exploring agents $a_{i}$ and
$a_{i+1}$ (where $i\in\\{1,2,\cdots,m-1\\}$) are performing a composite walk
by choosing their lowest available port at each new exploration.

  2. 2.

Whenever a pair of agents $a_{i}$ and $a_{i+1}$ reports back to the $h$, the
$LEADER$ updates their respective sequence of port numbers as well as their
respective length parameters.

  3. 3.

If the pair of agents fails to report, then the $LEADER$ after waiting for
$2(length[a_{i+1}]+2)$ rounds, activates another pair of agents $a_{i+3}$ and
$a_{i+4}$ in order to trace the path followed by the other pair.

    1. (a)

If the pair of agents find none of the agents $a_{i}$ or $a_{i+1}$ at the last
reported node, whereas the edge corresponding to the lowest available port
number is missing, then the agents $a_{i+3}$ and $a_{i+4}$ remains at that
node until the missing edge reappears.

      1. i.

If the edge does not reappear then $a_{i+3}$ and $a_{i+4}$ fails to report
then $LEADER$ after waiting for $2(length[a_{i+4}])$ rounds, activates another
pair of agents $a_{i+5}$ and $a_{i+6}$. They are instructed to perform a
composite walk along a port different from the one along which $a_{i+3}$ and
$a_{i+4}$ has traversed. Moreover, this pair is instructed to choose the
second lowest port whenever a choice of port numbers are available.

      2. ii.

Else if the edge reappears and $a_{i}$, $a_{i+2}$, $a_{i+3}$ and $a_{i+4}$
reunites together at a node, and while backtracking together fails to report
then

        1. A.

The agent $a_{i+4}$ elects itself sub-leader among $a_{i}$, $a_{i+2}$,
$a_{i+3}$ and $a_{i+4}$. Moreover, the pair of agents $a_{i+3}$ and $a_{i+4}$
remain at the stuck node, whereas $a_{i}$ and $a_{i+2}$ are instructed to
perform composite walk while reporting back to the sub-leader while it fails
to report back to $LEADER$.

        2. B.

The $LEADER$ after waiting for $2(length[a_{i+4}])$ rounds, activates another
pair of agents $a_{i+5}$ and $a_{i+6}$, which performs a composite walk along
a port different from the one along which $a_{i+3}$ and $a_{i+4}$ has
traversed. They further chooses the second lowest port, whenever a choice of
port numbers are available while exploring.

      3. iii.

Otherwise, the set of agents $a_{i}$, $a_{i+2}$, $a_{i+3}$ and $a_{i+4}$
return back to $h$.

    2. (b)

Otherwise, the pair of agents finds at least one of the agents among $a_{i}$
and $a_{i+2}$. Then they gather their information and starts backtracking
towards $h$.

      1. i.

If while backtracking fails to report, then the $LEADER$ after waiting for
$2(length[a_{i+4}])$ rounds, activates another pair of agents $a_{i+5}$ and
$a_{i+6}$. They are instructed to perform a composite walk along a port
different from the one along which $a_{i+3}$ and $a_{i+4}$ has traversed.
Moreover, this pair is instructed to choose the second lowest port whenever a
choice of port numbers are available.

      2. ii.

Else if the pair gathers the black hole information and returns back to $h$,
then the $LEADER$ terminates the algorithm.

      3. iii.

Otherwise, this pair after returning back to $h$ starts a composite walk along
unexplored areas of the graph.

  4. 4.

Otherwise, the pair of agents reports back to $h$.

    1. (a)

If the pair returns alone with the black hole information, then the algorithm
terminates.

    2. (b)

Else if the pair returns along with $a_{i}$ and $a_{i+2}$. Then $a_{i+3}$ and
$a_{i+4}$ starts a composite walk along unexplored areas of the graph, whereas
the agents $a_{i}$ and $a_{i+2}$ remains at $h$ until further reactivated.

    3. (c)

Otherwise, this pair $a_{i+3}$ and $a_{i+4}$ after returning back to $h$
alone, starts a composite walk along unexplored areas of the graph.

  5. 5.

If there is one remaining agent at $h$ except $LEADER$ and the $LEADER$ after
waiting for
$\underset{i\in\\{1,2,\cdots,2\alpha+4k+5\\}}{max}{\\{2(length[a_{i}]+2)\\}}$
rounds no pair of agents report back to $h$, then the $LEADER$ instructs the
remaining agent to perform pendulum walk and whenever it conveys the black
hole node information to the $LEADER$. The algorithm terminates.

Figure 6: A general cactus graph with multiple edge removal

####  4.2.2 Detailed Description:

Our algorithm $\mathcal{B}$ works with $2\alpha+4k+6$ agents, where one among
them is appointed as $LEADER$. Initially, $LEADER$ and all other agents are
co-located at a safe node $h$. Without loss of generality $deg(h)\geq 2$,
further we assume that all the ports are labeled in ascending order along the
counter-clockwise direction. To start with, two agents $a_{1}$ and $a_{2}$
gets activated at $h$ and begin a composite walk and travel along the lowest
port from $h$, whereas the remaining agents remain with $LEADER$ at $h$.
Whenever this pair of agent $a_{1}$ and $a_{2}$ has a choice of port numbers
to choose from, they choose the lowest port number among them. Each set of
agents perform a DFS traversal while executing a composite walk. Whenever a
pair of two agent explore a new node, they store the port number along which
they explored this new node and report back to $LEADER$. The $LEADER$
maintains a database, which stores a sequence of port numbers and the length
of path traversed by each set of agents. It increments the parameter
$length[a_{i}]$, where $i\in\\{1,2,\cdots,2\alpha+4k+5\\}$, whenever an agent
$a_{i}$ conveys a new port number to the $LEADER$. As the agents explore the
graph, the agents may have the following possibilities:

  * •

Possibility-1: An agent $a_{1}$ enters $BH$ node (refer the edge
$(SN_{BH},BH)$ in Fig. 5).

  * •

Possibility-2: An agent $a_{1}$ enters a node which is originally of 1-degree,
also termed as a pendant vertex (refer the edges $(h,PV)$ and $(SN,PV)$ in
Fig. 5 also refer the case, where $a_{1}$ enters the node $v_{17}$ in Fig. 6).

  * •

Possibility-3: $a_{1}$ and $a_{2}$ enters a node which is part of a cycle and
it is originally of degree two, but one of its edges is removed by the
adversary (refer the edges $(h,PV)$ and $(SN,PV)$ in Fig. 5 also refer Fig. 6
where $a_{1}$ has entered the node $v_{10}$).

  * •

Possibility-4: $a_{1}$ and $a_{2}$ while traversing along a cycle, got
separated by a missing edge (refer the situation, where $a_{1}$ is at the node
$v_{11}$ whereas $a_{2}$ is at the node $v_{10}$ in Fig. 6).

  * •

Possibility-5: $a_{1}$ and $a_{2}$ after exploring a new node along a cycle,
gets stuck by a missing edge while backtracking its way towards the $LEADER$
(refer the edge $(SN,PV|A)$ in Fig. 5 also refer the fact, where $a_{1}$ and
$a_{2}$ got stuck at the node $v_{10}$ in Fig. 6).

All the above possibilities, explain the situation when $a_{1}$ and $a_{2}$
are stuck at certain positions in the graph $\mathcal{G}$ and cannot return
back to the $LEADER$. So, the $LEADER$ waits for $2(length[a_{1}]+2)$ rounds,
and if none of the agents return back to $h$ to report then it activates
another pair of agent $a_{3}$ and $a_{4}$ to trace the path traversed by the
agents $a_{1}$ and $a_{2}$. Now, while tracing the path, we may have further
cases:

  * •

Case-1: When the agents $a_{3}$ and $a_{4}$ reach the last reported node of
$a_{1}$ and $a_{2}$. They find, these agents $a_{1}$ and $a_{2}$ are already
stuck at that node (refer the edges $(h,SN|A)$ and $(SN,SN|A)$ in Fig. 5).

  * •

Case-2: When the agents $a_{3}$ and $a_{4}$ reach the last reported node, they
find only the agent $a_{2}$ is stuck.

  * •

Case-3: When $a_{3}$ and $a_{4}$ reach the last reported node, they neither
find $a_{1}$ nor $a_{2}$, whereas the edge corresponding to the lowest port
number is missing (refer the case when $a_{1}$ and $a_{2}$ are at the node
$v_{11}$ whereas $a_{3}$ and $a_{4}$ reach the last reported node $v_{10}$ in
Fig. 6).

We investigate the strategy followed by the agents in each of the above cases.

In the first case, after finding the agents $a_{1}$ and $a_{2}$ stuck at the
last reported node, the agents $a_{3}$ and $a_{4}$ returns back to the
$LEADER$, and starts a composite walk along some other unexplored path.

In the second case, when the pair of agents $a_{3}$ and $a_{4}$ find only
$a_{2}$, then the reason why only $a_{2}$ can be found is explained with the
help of these following sub-cases:

  * •

Sub Case-1: The agent $a_{2}$ is stuck, due to a disappearing edge between
$a_{1}$ and $a_{2}$ (refer the situation when $a_{1}$ is at the node $v_{11}$
and $a_{2}$ is encountered by $a_{3}$ and $a_{4}$ at $v_{10}$ in Fig. 6).

  * •

Sub Case-2: The agent $a_{2}$ is stuck, due to the fact that $a_{1}$ has
entered the black hole node and the agent $a_{2}$ has knowledge about the
position of the black hole (refer the situation, when $a_{1}$ has entered $BH$
node, whereas $a_{2}$ is encountered at the node $v_{22}$ in Fig. 6).

In each of these above sub-cases, the agents $a_{3}$ and $a_{4}$ at first
visit the node at which $a_{2}$ is stuck. Now, in case of sub case-1, the
adversary may reappear this missing edge and disappear the edge adjacent to
this node, along the path towards the $LEADER$ (i.e., it may reappear the edge
$(v_{10},v_{11})$ whereas disappear the edge $(v_{9},v_{10})$ in Fig. 6).
Moreover, as the earlier missing edge reappears, hence $a_{1}$ returns back to
$a_{2}$, which is originally following the composite walk. Now in this case,
the agents $a_{1}$, $a_{2}$, $a_{3}$ and $a_{4}$ are all stuck at the same
node as they cannot return back, due to a missing edge along the path towards
the $LEADER$. Now to tackle this scenario, the agent $a_{4}$ is elected sub-
leader among these four agents. Further, the agents $a_{3}$ and $a_{4}$ remain
at the current node until there is no path back to $h$. In the meantime, the
agents $a_{1}$ and $a_{2}$ instead of waiting at this node, starts a composite
walk and reports back to sub-leader until the $LEADER$ is not reachable.

Otherwise, if this scenario does not arise, then the agents $a_{3}$ and
$a_{4}$ after gathering information from the $a_{3}$ tries to report back to
the $LEADER$. While returning back, these pair of agents may have to face
these further scenarios:

  * •

Scenario-1:If they successfully reach the $LEADER$, then they start a
composite walk along the other unexplored paths originating from this path
traversed by $a_{1}$ and $a_{2}$.

  * •

Scenario-2: $a_{3}$ and $a_{4}$ while returning back to the $LEADER$ gets
stuck by a missing edge. Now, since none of the agents $a_{1}$, $a_{2}$,
$a_{3}$ and $a_{4}$ returns to the $LEADER$ after waiting for $2length[a_{4}]$
rounds. The $LEADER$ understands that these agents are stuck in some cycle.
Hence, it decides to activate another pair of agents $a_{5}$ and $a_{6}$, and
sends them along a different port traversed by $a_{3}$ and $a_{4}$. The
movement of $a_{5}$ and $a_{6}$ are as follows: they perform a composite walk
and whenever they have a set of port numbers to choose from, they will choose
the second minimum port among them 111For example, when the agent $a_{5}$
tries to explore a new node, it finds a set $\\{\rho_{0},\rho_{1},\rho_{2}\\}$
of available port numbers. In this case, $a_{5}$ instead of choosing the port
$\rho_{0}$ chooses the port $\rho_{1}$ for its next traversal. If further they
get stuck at some node, then the $LEADER$ again waits for $2(length[a_{4}]+2)$
rounds, and if no agent $a_{5}$ or $a_{6}$ returns, then $LEADER$ further
activates two more agents in order to trace the path followed by $a_{5}$ and
$a_{6}$ and makes similar choices in terms of port numbers as done by $a_{5}$
and $a_{6}$.

Moreover, on the other hand if the agent $a_{1}$ has entered black hole, then
this information is provided to the agents $a_{3}$ and $a_{4}$ by $a_{2}$, and
they try to convey this information to the $LEADER$. If these pair of agents
successfully returns back to the $LEADER$, then the algorithm terminates.
Otherwise, if they get stuck while backtracking, the $LEADER$ performs a
similar strategy as discussed above in scenario-2.

In the third case (i.e., case-3), the agents $a_{3}$ and $a_{4}$, not finding
$a_{1}$ and $a_{2}$ at the other end of the missing edge, waits at that node,
until the edge reappears. In the meantime, the $LEADER$ after waiting for
$2(length[a_{4}]+2)$ rounds, activates $a_{5}$ and $a_{6}$ which moves along a
port different from the one traversed by $a_{3}$ and $a_{4}$. Moreover, this
set of agents $a_{5}$ and $a_{6}$ choose the second lowest port number
whenever there is a choice of port numbers to choose, as described in
scenario-2. This strategy follows recursively, until a single agent except the
$LEADER$ remains at the home base $h$. So, the $LEADER$ waits for
$\underset{i\in\\{1,2,\cdots,2\alpha+4k+5\\}}{max}{\\{2(length[a_{i}]+2)\\}}$
rounds, and if no pair of agent returns back to the home base after waiting
then this triggers the $LEADER$ to activate the remaining agent. The $LEADER$
instructs this agent to perform a pendulum walk along its movement and
whenever it finds any other agent it gathers its information and reports that
information back to the $LEADER$. Now, as the graph $\mathcal{G}$ contains at
most $\alpha+2k$ stuck points and all these stuck points in worst case are
occupied by at most $2\alpha+4k$ agents. In addition four other agents are
involved due to the black hole node. At this situation as all the stuck points
are occupied, and the black hole is detected by two set of agents. Hence, this
lone agent can traverse along the graph $\mathcal{G}$ and gather that
information and return back to the $LEADER$, which in turn terminates the
algorithm.

####  4.2.3 Correctness and Complexity:

In this section we show the correctness of the algorithm $\mathcal{B}$ and
number of agents required by the algorithm $\mathcal{B}$ in order to
successfully locate the black hole position.

###### Lemma 8

Given a dynamic cactus graph $\mathcal{G}$ and a team of agents executing the
algorithm $\mathcal{B}$ follows that, any stuck node in $\mathcal{G}$ can
stuck at most two agents.

###### Proof

Let there exists a stuck node $v$ in $\mathcal{G}$ which contains more than
two agents at any round. Now, observe that this stuck point is part of a
disappearing edge and hence part of a cycle. So, there is always an alternate
path to reach $h$. Then following the algorithm $\mathcal{B}$, one among them
becomes the sub-leader whereas the other pair of agents performs a composite
walk and reports back to the sub-leader until the $LEADER$ is not reachable.
Hence, while performing this walk it may either encounter the black hole or
another unoccupied 1-degree vertex or may reach $h$ as well. So, in any case
it does not get stuck at the node $v$. This contradicts our claim hence
proving the lemma. ∎

The next lemma gives a bound on the minimum number of agents that get consumed
while executing the algorithm $\mathcal{B}$.

###### Lemma 9

Given a dynamic cactus graph $\mathcal{G}$ with at most $k$ edges disappearing
and appearing in any round, then executing the algorithm $\mathcal{B}$ at most
two agents can enter the black hole.

###### Proof

Let us consider three consecutive nodes $\\{v_{0},v_{1},v_{2}\\}$ in
$\mathcal{G}$ and the agents are initially located at the home base $h$. So,
by observation 3.5, any agent must pass through either the node $v_{0}$ or
$v_{2}$ in order to reach the black hole. Now, according to the algorithm
$\mathcal{B}$, except the last agent, all the other agents move in a pair. So,
if one among them enters the black hole then the other stays at the adjacent
node. So, that whenever any other agent tries to reach the node $v_{1}$ from
either of the nodes $v_{0}$ or $v_{1}$, they get notified about the black hole
position. Hence, in worst case two agents try to enter the node $v_{1}$ from
two different sides and get consumed, whereas their accompanying agents occupy
the nodes $v_{0}$ and $v_{2}$ in order to shield other incoming agents from
entering the black hole. ∎

In this theorem, we give the bound on the number of agents required by the
algorithm $\mathcal{B}$ in order to successfully locate the black hole
position.

###### Theorem 4.3

Given a dynamic cactus graph $\mathcal{G}$, with $\alpha$ 1-degree nodes and
at most $k$ edges disappearing or appearing at any round. The algorithm
$\mathcal{B}$, requires at least $2\alpha+4k+6$ agents in order to
successfully locate the position of the black hole and convey the information
to the $LEADER$.

###### Proof

We prove the above claim by contradiction. Let, the algorithm $\mathcal{B}$
uses $2\alpha+4k+4$ agents except the $LEADER$, in order to successfully
locate the black hole position in $\mathcal{G}$. Now, as per the algorithm
$\mathcal{B}$, the $LEADER$ remains stationary at the home base, and instructs
the remaining agents either to perform a composite walk or to trace the
location of some stuck agents. The $LEADER$ activates a pair of agents, each
time such movement is necessary. Moreover, following the algorithm
$\mathcal{B}$ when an 1-degree node is detected by a pair of agents, they
remain stationary at that node until a new edge is detected. Now, in worst
case each disappearing edge constitutes of two 1-degree nodes. So, whenever
two separate pair of agents try to explore these pair of 1-degree nodes, they
remain stationary at those respective nodes. Now, according to the remark 2,
$\mathcal{G}$ has $\alpha+2k$ stuck points also by lemma 8, any stuck point
can occupy maximum two agents. Hence to cover $\alpha+2k$ nodes, the algorithm
$\mathcal{B}$ may engage maximum $2\alpha+4k$ agents, which remain stationary
at each of these nodes. Moreover, if the black hole node is a part of some
cycle, then by lemma 9 four additional agents are required, out of which two
agents gets consumed by the black hole and the remaining two agents acts as a
shield. So, in total all the agents $2\alpha+4k+4$ agents are either stuck or
acting as a shield or consumed by the black hole. In this scenario, neither
the $LEADER$ has any remaining agent left to be activated and explore the
graph nor it has the knowledge of the black hole position. Hence,
$2\alpha+4k+4$ excluding the $LEADER$ are not sufficient for the algorithm
$\mathcal{B}$, to convey the black hole information to the $LEADER$. ∎

###### Theorem 4.4

Given a dynamic cactus graph $\mathcal{G}$ with $\alpha$ many degree node and
at most $k$ many disappearing edges at any round, the algorithm $\mathcal{B}$
with $2\alpha+4k+6$ agents finds the black hole location with
$\mathcal{O}((\alpha+k)n^{2})$ moves.

###### Proof

Given a $n$ node dynamic cactus graph $\mathcal{G}$, it has at most
$\lfloor\frac{3(n-1)}{2}\rfloor$ many edges. Now following the algorithm
$\mathcal{B}$, a single edge can be traversed by a pair of agents at most
$3(n-1)+2$ many times. Hence, the total number of moves by a pair of agent is
at most $\left((3(n-1)+2)\lfloor\frac{3(n-1)}{2}\rfloor\right)$. Since, the
algorithm uses $(\alpha+2k)$ many pairs of agent. Hence, the total number of
moves required by algorithm $\mathcal{B}$ in order to successfully locate the
black hole position is at most
$\left((\alpha+2k)(3(n-1)+2)\lfloor\frac{3(n-1)}{2}\rfloor\right)$, i.e.,
$\mathcal{O}((\alpha+k)n^{2})$. ∎

##  5 Black Hole Search in Dynamic Cactus with Whiteboard

In this section, we present an algorithm to find the black hole by a team of
agents in presence of at most one dynamic edge. Our algorithm requires, each
node $v$ to have some local storage space, called whiteboard. The information
in the whiteboard can be assumed to be accessed by the agents in mutual
exclusion. Our algorithm solves the black hole search problem with the help of
3 agents $a_{1}$, $a_{2}$ and $a_{3}$, respectively. Among these three agents
a $LEADER$ is elected. We assume $a_{3}$ to be the $LEADER$ among them,
without loss of generality. The task of $LEADER$ is different from the other
two agents. The fundamental task of $LEADER$ is either to instruct an agent or
to conclude that certain agent has entered black hole, whereas the task of
agent is either to explore a unvisited node or trace a path explored by
another agent.

The movement of the agents $a_{1}$ and $a_{2}$ can be divided in to two
categories explore and trace:

  * •

In explore an agent performs either cautious walk or pendulum walk depending
on the instruction of $LEADER$. In this case, an agent visits a node for the
first time.

  * •

In trace an agent performs pendulum walk, where it visits a node which has
already been visited by another agent.

The task of the $LEADER$ can be explained as follows:

  * •

It instructs an agent to perform either cautious or pendulum walk.

  * •

It maintains a parameter $length[a_{i}]$, where $a_{i}\in\\{1,2\\}$ is
performing pendulum walk. The $LEADER$ increments $length[a_{i}]$ by 1,
whenever $a_{i}$ explore or trace a new node and report this information to
$LEADER$.

  * •

It terminates the algorithm whenever it knows the black hole position.

An agent $a_{i}$ (where $i\in\\{1,2\\}$) fails to report to $LEADER$, for the
following reasons:

  * •

It has entered the black hole.

  * •

It has encountered a missing edge.

There is no means of communication between any of these agents (including
$LEADER$), i.e., when two agents meet at a node they do not exchange any
gathered information. The only means of communication is through whiteboard.
Initially the whiteboards for each node is blank, whenever an agent visits a
node either writes on the whiteboard or follows certain direction already
written on the whiteboard. The contents of the whiteboard are as follows.

Whiteboard: For each node $v\in\mathcal{G}$ a whiteboard maintains a list of
information for each port, $\delta(v)$ at the node. More, precisely it
maintains a stack of visited ports $\rho_{j}$ (where
$\rho_{j}\in\\{\rho_{0},\cdots,\rho_{deg(v)-1}\\}$). Now, for each such
visited port $\rho_{j}$, the whiteboard stores a order tuples ($Explore[ID]$,
$Trace[ID]$, $Last.LEADER$), where $Explore[ID]$ stores the $ID$ of the agent
to first explore the port $\rho_{j}$, $Trace[ID]$ stores the $ID$ of the
tracing agent along $\rho_{j}$ and $Last.LEADER$ stores 1, if $\rho_{j}$ is
the last port in $v$ along which $LEADER$ has traversed, otherwise it stores
0. Once, a port is explored $Explore[ID]$ remains constant, whereas
$Trace[ID]$ and $Last.LEADER$ entries gets updated whenever an agent or
$LEADER$ passes along this port. Moreover, when an agent backtracks along a
port towards the $LEADER$, then no information is updated in the whiteboard.
Next, we discuss in detail the description of the algorithm.

Detailed Description: Our algorithm works with 3 agents: $a_{1}$, $a_{2}$ and
$a_{3}$, among them one is the $LEADER$. Let $a_{3}$ be designated as the
$LEADER$.

The agents $a_{1}$ and $LEADER$ start cautious movement, whereas $a_{2}$
performs pendulum movement and reports back to $LEADER$.

1 Initially $a_{i}$ is located at $home$ with $LEADER$, where $i\in\\{1,2\\}$.

2

3if  _$a_{i}$ performing cautious walk at $u$_ then

4 if  _each port is explored_ then

5 $a_{i}$ accompanies $LEADER$ and backtracks to a node which has at least one
port which is not explored.

6

7 else

8 $a_{i}$ chooses the first unexplored port $\rho_{j}$ to reach the node $v$
and correspondingly updates the whiteboard entry of port $\rho_{j}$ to
$(Explore[a_{i}],0,0)$ at $u$.

9 It travels along $\rho_{j}$ to a node $v$, following the edge $e=(u,v)$.

10 if  _$v$ is safe and $e$ remains_ then

11 $a_{i}$ returns back to $u$ and takes $LEADER$ to $v$.

12

13 else if  _$v$ is safe and $e$ is missing_ then

14 $a_{i}$ remains stationary at $v$ until the edge reappears.

15

16

17

18else if  _$a_{i}$ performing pendulum walk at $u$_ then

19 if  _each port is explored by $a_{i}$_ then

20 $a_{i}$ backtracks to the node which has at least one port not visited by
$a_{i}$.

21 if  _$a_{i}$ encounters a missing edge while backtracking_ then

22 It remains stationary until the edge reappears.

23

24

25 else if  _at least one port is not explored by $a_{i}$_ then

26 $a_{i}$ chooses a port $\rho_{j}$ among them.

27 if  _$\rho_{j}$ is explored by some other agent_ then

28 $a_{i}$ travels along $\rho_{j}$ to a node $v$ from $u$ and updates
$Trace[ID]\longleftarrow Trace[a_{i}]$ at $u$ for $\rho_{j}$. Then it starts
backtracking to $LEADER$.

29 if  _$a_{i}$ encounters a missing edge while backtacking_ then

30 It remains stationary until the missing edge reappears.

31

32

33 else

34 $a_{i}$ travels along $\rho_{j}$ to a node $v$ from $u$ and updates
$Explore[ID]\longleftarrow Explore[a_{i}]$ at $u$ for the node $\rho_{j}$.
Then it starts backtracking towards $LEADER$.

35 if  _$a_{i}$ encounters a missing edge while backtracking_ then

36 It remains stationary until the missing edge reappears.

37

38

39

40

Algorithm 1 Algorithm for Agents $a_{1}$ and $a_{2}$

1 Set $length[a_{1}]=length[a_{2}]=0$.

2 Initially $LEADER$ is accompanied by $a_{1}$ and $a_{2}$ at $home$.

3 It instructs $a_{1}$ to perform cautious walk and $a_{2}$ to perform
pendulum walk.

4 Whenever $LEADER$ reaches a node $v$ from $u$ along a port $\rho_{j}$, it
updates $Last.LEADER$ of $\rho_{j}$ to 1 and all the other $Last.LEADER$ at
$u$ to 0.

5 When an agent $a_{i}$ performing pendulum walk reaches back to $LEADER$, it
increments $length[a_{i}]=length[a_{i}]+1$, where $i\in\\{1,2\\}$.

6 if  _$a_{1}$ fails to report_ then

7 if  _the edge along which $a_{1}$ travelled is present_ then

8 $LEADER$ waits for one round, and concludes $a_{1}$ has entered black hole
and terminates the algorithm.

9

10 else

11 $LEADER$ remains stationary at the other end of the missing edge, until it
reappears, whereas $a_{2}$ performs its movement.

12

13

14else if  _$a_{2}$ fails to report_ then

15 $LEADER$ after waiting for $2(length[a_{2}]+1)$ rounds, decides to move
towards $a_{2}$ by following the whiteboard instruction, while updating the
$Last.LEADER$ in whiteboard. It also instructs $a_{1}$ to stop cautious walk
and start pendulum walk.

16 if  _$LEADER$ finds $a_{2}$_ then

17 if  _the missing edge adjacent to $a_{2}$ does not reappear_ then

18 if  _$a_{1}$ fails to report_ then

19 $a_{2}$ remains stationary and $LEADER$ after waiting for
$2(length[a_{1}]+1)$ rounds, concludes that $a_{1}$ has entered black hole,
and traverses to the last reported node of $a_{1}$ following the whiteboard
instruction to detect the location of the black hole and terminate the
algorithm.

20

21 else

22 $a_{2}$ and $LEADER$ remain stationary together.

23

24

25 else

26 if  _$a_{1}$ fails to report_ then

27 $LEADER$ moves towards $a_{1}$, while instructing $a_{2}$ to continue
pendulum walk.

28

29 else

30 $a_{1}$ continues its pendulum walk, whereas $LEADER$ instructs $a_{2}$ to
perform cautious walk.

31

32

33

34 else if  _$LEADER$ finds a missing edge_ then

35 It remains stationary until the missing edge reappears.

36

37 else

38 $LEADER$ waits for one round, and concludes that $a_{2}$ has entered black
hole and terminates the algorithm.

39

40

Algorithm 2 Algorithm for $LEADER$