#  Pebble Guided Near Optimal Treasure Hunt in Anonymous Graphs 111
Preliminary version of this paper is accepted in SIROCCO 2021.

Barun Gorain222 Indian Institute of Technology Bhilai, Raipur, Chattisgarh,
India<EMAIL_ADDRESS>Kaushik Mondal333 Indian Institute of Technology
Ropar, Rupnagar, Punjab, India<EMAIL_ADDRESS>Himadri Nayak444
Indian Institute of Information Technology, Bhagalpur, India
<EMAIL_ADDRESS>Supantha Pandit555 Dhirubhai Ambani Institute of
Information and Communication Technology, Gandhinagar, Gujrat, India.
<EMAIL_ADDRESS>
###### Abstract

We study the problem of treasure hunt in a graph by a mobile agent. The nodes
in the graph are anonymous and the edges at any node $v$ of degree $deg(v)$
are labeled arbitrarily as $0,1,\ldots,deg(v)-1$. A mobile agent, starting
from a node, must find a stationary object, called treasure that is located on
an unknown node at a distance $D$ from its initial position. The agent finds
the treasure when it reaches the node where the treasure is present. The time
of treasure hunt is defined as the number of edges the agent visits before it
finds the treasure. The agent does not have any prior knowledge about the
graph or the position of the treasure. An Oracle, that knows the graph, the
initial position of the agent, and the position of the treasure, places some
pebbles on the nodes, at most one per node, of the graph to guide the agent
towards the treasure.

We target to answer the question: what is the fastest possible treasure hunt
algorithm regardless of the number of pebbles are placed?

We show an algorithm that uses $O(D\log\Delta)$ pebbles to find the treasure
in a graph $G$ in time $O(D\log\Delta+\log^{3}\Delta)$, where $\Delta$ is the
maximum degree of a node in $G$ and $D$ is the distance from the initial
position of the agent to the treasure. We show an almost matching lower bound
of $\Omega(D\log\Delta)$ on time of the treasure hunt using any number of
pebbles.

Keywords: treasure hunt, mobile agent, anonymous graph, pebbles

##  1 Introduction

###  1.1 Model and Problem Definition

Treasure hunt by a mobile agent is a well studied problem in networks and
related areas. A mobile agent, starting from an initial position, has to find
a stationary object, called treasure. In practice, a treasure can be a missing
person in a dark cave and a mobile robot must find the person. In networks
applications, a software agent must find a computer virus or valuable data
resource in a computer connected in a network.

The network is modeled as a graph where the nodes are unlabeled. The edges at
a node $v$ of degree $deg(v)$ are labeled as $0,1,\ldots,deg(v)-1$
arbitrarily. Thus, each edge has two port numbers associated with it at each
of its incident vertices. A mobile agent, starting from a node, must find the
treasure which is situated in an unknown node at distance $D$. The agent have
no prior knowledge about the network or the value of $D$. The agent finds the
existence of the treasure only when it reaches the node where the treasure is
situated. The agent moves according to a deterministic algorithm where at each
node, it chooses a port and move to the next node using the chosen port. At
the start, the agent only knows the degree of the initial node. From a node
$u$, when the agent reaches node $v$ by using the port $p$ at $u$, it learns
the degree of the node $v$, and the port $q$ at $v$ through which it reaches
$v$. For a network with maximum degree $\Delta$, using a simple depth first
search based algorithm, the agent can find the treasure in time
$O(\Delta^{D})$. But many practical applications required a faster treasure
hunt algorithm. For example, consider the application of finding a person
inside a mine by a mobile robot. The person may be lost and injured due to a
sudden accident and therefore he or she must be found as fast as possible. In
such scenarios, some external help is provided to the robot/agent in order to
guide it towards the desired location faster. Providing such external help is
often done by an oracle which gives some additional information in the form of
a binary string, called advice [13, 18]. The oracle gives this advice to the
agent a priori. Using the information provided in the advice, the agent finds
the treasure. However, if the treasure hunt has to be done by sufficiently
large number of agents independently over a long duration, providing such
advice to each of the agents might be costly. Instead, the same purpose can be
served by providing information to the nodes of the networks only once. Each
agent, while visiting a node, learns this information and find the treasure
using it. In this paper, we consider a very simple scenario where a pebble can
be placed at the nodes as an external information. An agent, looking at the
placement of the pebbles, learns in which way it must traverse to find the
treasure. To be specific, we consider the problem where some pebbles are
placed in some nodes of the network by an oracle who knows the initial
position of the agent and the position of the treasure. The position of the
pebbles guides the agent towards the treasure. At any node, at most one pebble
can be placed. The agent can see a pebble only after reaching that node. In
this paper, we study what is the fastest possible algorithm for treasure hunt
in anonymous graphs with pebbles. To be specific, we aim design the fastest
algorithm for treasure hunt when any number of pebbles can be placed in the
network.

###  1.2 Our Result

  * ➤

We present an algorithm that finds the treasure in an anonymous graph in
$O(D\log\Delta+\log^{3}\Delta)$-time using $O(D\log\Delta)$ pebbles, where
$\Delta$ is the maximum degree of a node in the graph and $D$ is the distance
from the initial position of the agent to the treasure.

  * ➤

We prove that even if we supply any number of pebbles, any algorithm must
require $\Omega(D\log\Delta)$-time to find the treasure in an anonymous graph.

###  1.3 Related Work

Treasure hunt by a mobile agent is a well studied problem [3, 6, 7, 9, 11, 15,
18, 22] for last few decades. In [3], Beck et al. introduced the problem of
deterministic treasure hunt on a line. The authors proposed a deterministic
algorithm with competitive ratio 9 and proved that this ratio is the best that
can be acheived in case of line. A generalized version of [3] was studied by
Demaine et al. [9] by considering cost of turns that agent makes along with
the cost of the trajectory. Bouchard et al. [7] considered the treasure hunt
problem in plane and showed a much improved bound with the assumption of angle
information.

In the book [1], several problems related to treasure hunt are discussed. Most
of the algorithms surveyed in this book are randomized. One such is the
randomized treasure hunt in a star, where the treasure is present in one of
the $m$ rays passing through a common point [15]. In [18, 22], it is shown
that the problem of treasure hunt and the problem of rendezvous in graphs are
closely related. Ricardo et al. studied the problem of finding an unknown
fixed point on a line and in a grid [2]. More generalized studies are done in
[14, 16], where the objective is to search an unknown line in a plane. The
author studied the problem of finding a target in a ring in [21] by multiple
selfish agents participates and a game theoretic solution is proposed. Also,
treasure hunt in a plane and in a grid by multiple agents are studied in [11,
12, 17]. In [11, 17], the agents are considered to have bounded memory.
Treasure hunt in plane is studied in [20] in the advice model. Treasure hunt
in a tree network is studied in [4], where random faulty hints are provided to
the agents. Treasure hunt in arbitrary graph is also studied in [6]
considering the agent has unlimited memory. The game of pursuit-evasion, a
closely related problem to treasure hunt, is considered in [5, 8], where set
of pursuers try to catch a fugitive trying to escape. Also treasure hunt in
terrain in presence of obstacles was introduced in [19]. Another related
problem is graph exploration and Disser et. al. [10] recently proved a tight
bound on number of pebbles required for a single mobile agent with constant
memory to explore an undirected port labelled graph.

##  2 Treasure Hunt Algorithm

In this section, we provide an $O(D\log\Delta+\log^{3}\Delta)$-time algorithm
for the treasure hunt problem using $O(D\log\Delta)$ pebbles.

Let $G$ be a graph with maximum degree $\Delta\geq 2^{10}$. If
$\Delta<2^{10}$, then the algorithm described for the case when all nodes on
the path from $s$ to $t$ are of ‘small’ degree (these small degree nodes are
defined as light nodes later) can be applied.

Let $s,t\in G$ be the starting point of the agent, and position of the
treasure in $G$, respectively. Let $P$ be the shortest path between $s$ and
$t$ of length $D$. Without loss of generality, we assume that the degree of
the node $s$ is at least 2. Otherwise, the first degree-3 node along $P$
starting from $s$ can be considered as the starting position of the agent. For
any node $v\in G$, by $deg(v)$, we denote the degree of the node $v$. Let
$\alpha_{v}=1+\lfloor\log deg(v)\rfloor$. For any node $w\in G$, by
$w(0),w(1),\ldots,w(deg(w)-1)$, we denotes the neighbors of $w$ that are
connected through port numbered $0,1,\ldots,deg(w)-1$, at $w$ respectively.
For any two strings $\Gamma_{1}$ and $\Gamma_{2}$, by
‘$\Gamma_{1}\cdot\Gamma_{2}$’, we mean concatenation of $\Gamma_{1}$ and
$\Gamma_{2}$. For any binary string $\Gamma$, by $\Gamma(i,j)$, we denote the
substring of $\Gamma$ starting from the $i$-th bit of $\Gamma$ to the $j$-th
bit of $\Gamma$. For two nodes $u,v\in G$, we denote the shortest distance
between $u$ and $v$ in $G$ by $dist(u,v)$.

Before providing the formal description of the algorithm, we give a high level
idea of the pebble placement and discuss how these pebbles guide the agent
towards the treasure. To help the reader understand the algorithm better, we
describe the idea for trees first and then generalize this idea for general
graphs.

High level idea of the algorithm in a tree network: Here we assume that $G$ is
a rooted tree with root $s$. Let $L_{i}$ be the set of nodes that are at
distance $i$ from $s$. Let $P=(s=)~{}v_{0},v_{1},\ldots,v_{D-1},v_{D}~{}(=t)$
be the path from $s$ to $t$, and let $p_{0},p_{1},\ldots,p_{D-1}$ be the
sequence of port numbers corresponding to the path $P$ such that from the node
$v_{\ell}$, the node $v_{\ell+1}$ can be reached by taking the edge with port
number $p_{\ell}$. For any node $v\in L_{j}$, let its $i$-th neighbor be the
adjacent node in $L_{j+1}$ to which $v$ is connected via $i$-th largest port
going to $L_{j+1}$. The pebbles are placed at the children of the nodes in $P$
such that the placement of the pebbles corresponds the binary representation
of the port numbers along the shortest path from the current node. To be more
specific, let $b_{0}b_{1}\ldots b_{m-1}$ be the binary representation of the
integer $p_{j}$, where $m=1+\lfloor\log deg(v_{j})\rfloor$. For $0\leq i\leq
m-1$, place a pebble at $i$-th neighbor of $v_{j}$, if $b_{i}=1$. Hence, from
the point of view of a node $v_{j}\in L_{i}$, each of its neighbors in
$L_{i+1}$ either contains a pebble or does not contain a pebble. Visiting each
of the neighbor in increasing order of the port numbers and ignoring the port
that connects to the parent of the current node, the agent, from the current
node, can learn the binary representation of the integer $p_{j}$, by realizing
a node with pebble as ‘1’ and a node without pebble as ‘0’. Hence, the
placement of pebbles in the above manner helps us to “encode” the port labeled
path from $s$ to $t$ and the agent, with the help of this encoding, learn the
port numbers from each node in $P$ that leads to the next node towards the
treasure. The difficulty here for the agent is while learning this binary
encoding by looking at the pebble placement, the agent must learn when this
binary encoding ends, as the nodes, which are not used for encoding (no
pebbles are placed on these nodes) can be misinterpreted as zeros. To overcome
this difficulty, instead of simple binary encoding. we use a transformed
binary encoding: replacing every ‘1’ by ‘11’ and every ‘0’ by’ ‘10’ in the
standard binary encoding. The advantage of this transformed encoding is that
it does not contain the substring ‘00’. Hence, as soon as the agent sees two
consecutive node without pebbles, it realizes that the binary string that is
encoded in the nodes is ended.

Extending the idea for general graphs: The above method of pebble placement
for trees can not be directly extended to general graphs. This is because in a
rooted tree, no two nodes have common children. Hence, once the encoding is
done after placing the pebbles, the agent can unambiguously decode this
encoding. However, in the case of graphs, two consecutive nodes on $P$ may
have neighbors in common. Hence, if a pebble is placed on such a common
neighbor, the agent can not distinguish for which node the pebble is placed.
Also, since the nodes are anonymous, there is no way the agent can identify
whether it is visiting a node that is a common neighbor to the previous or
next node. We resolve this difficulty by encoding in the neighbors of a set of
“high” degree nodes that do not share neighbors. These nodes are called
milestones (we define this formally later). The details are explained below.

We say that a node is heavy if its degree is at least
$80\lfloor\log\Delta\rfloor+106$ (the reason for choosing this magical number
is discussed in Remark 2.1). Otherwise, we say that the node is light. Let $T$
be the breadth first search (BFS) tree, rooted at $s$, and for $0\leq i\leq
D$, let $L_{i}$ denotes the set of nodes that are at a distance $i$ from $s$.
Clearly, $s\in L_{0}$, and $t\in L_{D}$.

Let $P=(s=)~{}v_{0},,v_{1},\ldots,v_{D-1},v_{D}~{}(=t)$, be the shortest path
from $s$ to $t$, and let $p_{0},p_{1},\ldots,p_{D-1}$ be the sequence of port
numbers corresponding to the path $P$ such that from the node $v_{\ell}$, the
node $v_{\ell+1}$ can be reached by taking the edge with port number
$p_{\ell}$, for $0\leq\ell<D$. For $0\leq i\leq D-1$, let $B_{i}$ be the
binary representation of the integer $p_{i}$ of length $x_{i}$, where
$x_{i}=1+\lfloor\log deg(v_{i})\rfloor$.

First, consider a special case where each $v_{i}$, $0\leq i\leq D-1$, is
light. A simple algorithm will work in this case: place a pebble at each of
the nodes $v_{i}$, for $1\leq i\leq D-1$. The agent, at the starting node $s$,
set $CurrentNode=s$. At each step, the agent visits all the neighbors of the
$CurrentNode$ and move to the neighbor $v$, (except the node from where it
reaches to $CurrentNode$) that contains a pebble. It then sets
$CurrentNode=v$. The agent continues to explore in this way until the treasure
is found. Since all the nodes on $P$ are light, the time for treasure hunt is
$O(D\log\Delta)$. If not all nodes are light on $P$, then a set of nodes
called milestones are used to code the sequence of port numbers corresponding
to the path $P$. We define a set of nodes as milestones in a recursive manner.
To define the first milestone, we consider the following four cases based on
the position of the heavy nodes in the BFS tree $T$: i) the node $s$ is heavy,
ii) the node $s$ is light and a node in $L_{1}$ is heavy, iii) all the nodes
in $L_{0}\cup L_{1}$ are light and a node in $L_{2}$ is heavy, and iv) all the
nodes in $L_{0}\cup L_{1}\cup L_{2}$ are light and $j\geq 3$ is the smallest
integer for which $L_{j}$ contains a heavy node that is at a distance 3 from
$v_{j-3}$. From now onward, we distinguish these four cases as Case H, Case
L-H, Case L-L-H, and Case L-L-L, respectively.

The first milestone is defined based on the above four cases as follows.

  * •

Case H: $milestone_{1}=s$.

  * •

Case L-H: Let $w$ be the node with maximum degree in $L_{1}$. If multiple
nodes with maximum degree exists, then $w$ is chosen as the node to which $s$
is connected by the edge with minimum port number. Set $milestone_{1}=w$.

  * •

Case L-L-H: Let $w$ be the node with maximum degree in $L_{2}$. If multiple
nodes with maximum degree exists, then $w$ is chosen as the node to which $s$
is connected by a path of length 2 which is lexicographically shortest among
all other paths to nodes with same degree. Set $milestone_{1}=w$.

  * •

Case L-L-L: If $j=4$, and $v_{1}\in\\{s(0),s(1)\\}$, then consider the set
$W=\\{w\in L_{j}|dist(s(0),w)=3~{}or~{}dist(s(1),w)=3\\}$. Let $w$ be the node
in $W$ whose degree is maximum among all nodes in $W$. If multiple nodes with
maximum degree exists, then the node with maximum degree to which $s$ is
connected via lexicographically shortest path of length 4 is chosen as $w$.
Set $milestone_{1}=w$. On the other hand, If $j>4$ or
$v_{1}\not\in\\{s(0),s(1)\\}$, let $W=\\{w\in L_{j}|dist(v_{j-3},w)=3\\}$. Let
$w$ be the node with maximum degree in $W$. If multiple nodes with maximum
degree exists then $w$ is chosen as the node to which $v_{j-3}$ is connected
by a path of length 3 that is lexicographically shortest among all other nodes
with same degree. Set $milestone_{1}=w$.

The subsequent milestones are defined recursively as follows. For $i\geq 1$,
let $milestone_{i}\in L_{j}$. The first heavy node on $P$ that is at a
distance at least 3 from $v_{j}$ is defined as $milestone_{i+1}$.

Intuitively, we encode in the neighbors of the milestones in a similar fashion
as described above for the case of tree network. As the milestones are at
least 3 distance apart, no two of them have common neighbors and hence
decoding can be done unambiguously. However, there is another difficulty, that
is the agent does not have any knowledge about the graph and hence does not
know the value of $\Delta$, the maximum degree of the graph. This restrict the
agent to learn whether a node is heavy or light just by looking at its degree.
We overcome this difficulty by placing some ‘markers’. By looking at these
markers the agent can identify the possible position of the first milestone.
Once the agent identify the first milestone, finding the other milestones are
easy as the path towards the next milestone is carefully coded at the
neighbors of the current milestone. If $s$ itself is a heavy node, then it is
defined as the first milestone. In order to help the agent to learn that this
is the case, two pebbles are placed at $s(0)$, and $s(1)$, one at each. The
agent, at the beginning of the treasure hunt algorithm, first visits the first
two neighbors of $s$, and learn that $s$ is heavy, if it sees pebbles at both
of these nodes. If $s$ is light and a node in $L_{1}$ is heavy, then a pebble
is placed at $s(0)$. While vising first two neighbors of $s$, the agent
identify the Case L-H by finding a pebble at $s(0)$, and not finding any
pebble at $s(1)$. Once the agent identify the Case L-H, it reach to the node
connected to $s$ with maximum degree and hence reach to the first milestone in
this case. For Case L-L-H, a pebble is placed at $s(1)$. In similar fashion as
earlier, the agent identify the Case L-L-H, by finding a pebble at $s(1)$, and
not finding any pebble at $s(0)$. It then reached to the milestone by
exploring all paths of length 2 from $s$ and finding the node with maximum
degree. For the Case L-L-L, no pebbles are placed in either of the first two
neighbors of $s$ and the agent can identify this case by visiting $s(0)$ and
$s(1)$ and not finding any pebbles in these nodes. We explain how the agent
identify the first milestone in this case later where formal description of
the algorithm is provided.

Another set of ‘markers’ are used to indicate the distance between two
consecutive milestones. How these markers are placed will be explained later
where formal descriptions of the pebble placements is provided.

We are ready to give the formal description of the treasure hunt algorithm.

####  2.0.1 Pebble Placement:

The placement of pebbles are done in three phases.

Phase 1: Placing pebbles in $s(0)$ and $s(1)$

  * •

Case H: Place one pebble each at $s(0)$, and $s(1)$.

  * •

Case L-H: Place a pebble at $s(0)$.

  * •

Case L-L-H: Place a pebble at $s(1)$.

  * •

Case L-L-L: No pebble is placed in $s(0)$, and $s(1)$ is this case.

Phase 2: Placing pebbles to encode the path between $milestone_{1}$ to
$milestone_{2}$

Case H: Here $milestone_{1}$ is the node $s$ itself. Notice that, two pebbles
are already placed at $s(0)$ and $s(1)$ during phase 1 to represent the marker
corresponding to Case H. The other neighbors of $s$ are used to encode the
path say $P^{\prime}$ from $s$ to $milestone_{2}$. To be more specific, if the
distance from $s$ to $milestone_{2}$ is at most 5, then the entire path
$P^{\prime}$ is coded in the neighbors of $s$. Otherwise, if the distance from
$s$ to $milestone_{2}$ is more than 5, then the first three port numbers and
the last three port numbers are encoded at the neighbors of $s$. The
difficulty here is to make the agent learn that how far $milestone_{2}$ is
from $s$. To overcome this situation, the third neighbor $s(2)$ and the fourth
neighbor $s(3)$ of $s$ are used as ‘markers’ to represent the distance between
$s$ to $milestone_{2}$. To denote that $milestone_{2}$ is at distance 3, two
pebbles are placed on $s(2)$ and $s(3)$ to encode the marker ‘11’. To denote
$milestone_{2}$ is at distance 4, a pebble is placed on $s(2)$ and no pebble
is placed on $s(3)$ to encode the marker ‘10’. To denote $milestone_{2}$ is at
distance 5, a pebble is placed on $s(3)$ and no pebble is placed on $s(2)$ to
encode the marker ‘01’. Finally, no pebbles are placed either on $s(2)$ or on
$s(3)$ to encode the marker ‘00’ that indicates that $milestone_{2}$ is at
least 6 distance apart from $milestone_{1}$. Note that in this case,
($milestone_{2}$ is at distance more than 5 from $milestone_{1}$) the entire
path from $milestone_{1}$ to $milestone_{2}$ is not coded. Instead, the first
three and the last three sequence of port numbers are coded in the neighbors
of $milestone_{1}$. Once the agent learns this coding, can compute the first
three ports and The light nodes in between are used to guide the agent towards
$milestone_{2}$.

Once the pebble corresponding to markers are placed, a few other neighbors of
$s$ are used to encode the sequence of port numbers following which the agent
reaches $milestone_{2}$ from $milestone_{1}$. The formal pebbles placement is
described based on the distance of the second milestone as follows. Let $\ell$
be an integer such that $milestone_{2}=v_{\ell}$.

  1. 1.

$\left[\ell=3\right]$: Here the path from $milestone_{1}$ to $milestone_{2}$
is $v_{0},v_{1},v_{2},v_{3}$ and the corresponding sequence of port numbers is
$p_{0},p_{1},p_{2}$. Let $\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}$ and
$\Gamma=11\cdot\Gamma^{\prime}$.

  2. 2.

$\left[\ell=4\right]$: Here the path from $milestone_{1}$ to $milestone_{2}$
is $v_{0},v_{1},v_{2},v_{3},v_{4}$ and the corresponding sequence of port
numbers is $p_{0},p_{1},p_{2},p_{3}$. Let $\Gamma^{\prime}=B_{0}\cdot
B_{1}\cdot B_{2}\cdot B_{3}$ and $\Gamma=10\cdot\Gamma^{\prime}$.

  3. 3.

$\left[\ell=5\right]$: Here the path from $milestone_{1}$ to $milestone_{2}$
is $v_{0},v_{1},v_{2},v_{3},v_{4},v_{5}$ and the corresponding sequence of
port numbers is $p_{0},p_{1},p_{2},p_{3},p_{4}$. Let
$\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}$ and
$\Gamma=01\cdot\Gamma^{\prime}$.

  4. 4.

$\left[\ell\geq 6\right]$: Here the path from $milestone_{1}$ to
$milestone_{2}$ is $v_{0},v_{1},\ldots v_{\ell}$ and the corresponding
sequence of port numbers is $p_{0},p_{1},\ldots p_{\ell}$. As mentioned
earlier, the sequence of port numbers
$p_{0},p_{1},p_{2},p_{\ell-3},p_{\ell-2},p_{\ell-1}$ is coded in this case.
Let $\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{\ell-3}\cdot
B_{\ell-2}\cdot B_{\ell-1}$ and $\Gamma=00\cdot\Gamma^{\prime}$.

Let $\hat{\Gamma}$ be the transformed binary encoding of $\Gamma$. Let $z$ be
the length of the string $\hat{\Gamma}$. For $1\leq i\leq z$, place a pebble
on $s(1+i)$, if the $i$-th bit of $\hat{\Gamma}$ is 1. If $\ell\geq 7$, then
place a pebble on each of the nodes $v_{4},\ldots,v_{\ell-3}$.

Figure 1 shows the pebble placement for Case H.

(a)

(b)

(c)

(d)

Figure 1: Showing the pebble placement in Case H. The markers are represented
by showing pebbles using gray colored circles above the nodes (a) Placement of
pebbles where $milestone_{2}\in L_{3}$ (b) Placement of pebbles where
$milestone_{2}\in L_{4}$ (c) Placement of pebbles where $milestone_{2}\in
L_{5}$ (d) Placement of pebbles where $milestone_{2}\in L_{j}$ for $j\geq 6$.

Case L-H: In this case, the first milestone is selected as one of the
neighbors $w$ of $s$. Note that $w$ may not be on the shortest path from $s$
to $t$. For this reason we encode the path (or a subpath of the path) from $s$
to $milestone_{2}$ in the neighbors of $w$. The agent, while executing the
treasure hunt algorithm, first arrives at $w$, decode the path which is
encoded in the neighbors of $w$, returns back to $s$ and then moves according
to this learned path.

In order to encode the path from $s$ to $milestone_{2}$, a similar approach as
in Case H can be applied. The sequence of port numbers from $s$ to
$milestone_{2}$ is encoded in the neighbors of $w$. As before, this is done
based on the distance from $s$ to $milestone_{2}$. However, a difficulty
arises as $s(0)$ and/or $s(1)$ may also be neighbours of $w$ and there is no
way for the agent to learn through which port $w$ is connected to $s(0)$ or
$s(1)$. We overcome this difficulty in the following way.

Let $\Gamma$ be the binary string of length $z$ that we want to encode in the
neighbors of $w$. Let $N_{1}(w),N_{2}(w),\ldots,N_{5}(w)$ be 5 sets of
disjoint neighbors of $w$ and the cardinality of each set is $z$. Since $s(0)$
and/or $s(1)$ may be neighbours of $w$, at least 3 of these 5 neighbour sets
of $w$ does not contain either $s(0)$ or $s(1)$. This implies that, if
$\Gamma$ is coded in each of these five sets, it is possible to code $\Gamma$
correctly (without interrupting $s(0)$ and $s(1)$ for which pebble placement
is already done in Phase 1) in the nodes of three sets. Hence, while executing
the treasure hunt algorithm, if the agent learns all the strings that are
coded in these five sets, then $\Gamma$ can be identified as the string that
is coded in majority number of sets. To be specific, the nodes of each of the
$N_{i}(w)$ to encode $\Gamma$, and if $s(0)$ or $s(1)$ appears in this set
then skip the corresponding bits of $\Gamma$ while placing pebbles at the time
of coding. Another difficulty here is how to make the agent learn where the
set $N_{i}(w)$ ends and $N_{i+1}(w)$ starts. To overcome this difficulty,
instead of simple binary encoding of the sequence of port numbers as explained
in Case H, we use a transformed binary encoding: replace every ‘1’ by ‘11’ and
every ‘0’ by ‘10’ of $\Gamma$. The advantage of this transformed encoding is
that it does not contains the substring 00. We take advantage of this fact to
show separation between the sets $N_{i}(w)$s as follows. First, compute the
string $\Gamma$ that has to be encoded in the neighbors of $w$. Compute the
transformed encoding $\hat{\Gamma}$. Now, encode $\hat{\Gamma}$ in $N_{i}(w)$
and next two neighbors after $N_{i}(w)$ are left blank (no pebbles placed to
represent ‘00’). The agent continues to visit consecutive neighbors of $w$
until it sees two consecutive nodes that does not contains any pebbles. At
this point the agent learns that here the set $N_{i}(w)$ ends. One more
difficulty can arise in which the nodes which are left blank may also contain
$s(0)$ or $s(1)$. We later show that $\hat{\Gamma}$ still can unambiguously
computed by the agent.

The formal description of the placement of pebbles in this case is given
below. Let $milestone_{2}=v_{\ell}$. Note that as per the definition of
milestones, $l\geq 4$.

  1. 1.

$\left[\ell=4\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},v_{2},v_{3},v_{4}$ and the corresponding sequence of port numbers
is $p_{0},p_{1},p_{2},p_{3}$. Let $\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot
B_{2}\cdot B_{3}$ and $\Gamma=11\cdot\Gamma^{\prime}$.

  2. 2.

$\left[\ell=5\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},v_{2},v_{3},v_{4},v_{5}$ and the corresponding sequence of port
numbers is $p_{0},p_{1},p_{2},p_{3},p_{4}$. Let $\Gamma^{\prime}=B_{0}\cdot
B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}$ and $\Gamma=10\cdot\Gamma^{\prime}$.

  3. 3.

$\left[\ell=6\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$ and the corresponding sequence of
port numbers is $p_{0},p_{1},p_{2},p_{3},p_{4},p_{5}$. Let
$\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}\cdot B_{5}$
and $\Gamma=01\cdot\Gamma^{\prime}$.

  4. 4.

$\left[\ell\geq 7\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},\ldots v_{\ell}$ and the corresponding sequence of port numbers
is $p_{0},p_{1},\ldots,p_{\ell}$. In this case, the sequence of port numbers
$p_{0},p_{1},p_{2},p_{3},p_{\ell-3},p_{\ell-2},p_{\ell-1}$ is coded. Let
$\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{\ell-3}\cdot
B_{\ell-2}\cdot B_{\ell-1}$ and $\Gamma=00\cdot\Gamma^{\prime}$.

Let $\hat{\Gamma}$ be the transformed binary encoding of $\Gamma$ and $z$ is
the length of $\hat{\Gamma}$. Let $N_{i}(w)$, for $1\leq i\leq 5$, be the set
$z$ consecutive neighbors of $w$ starting from the node $w((i-1)(z+2))$. To be
specific,
$N_{i}(w)=\\{w((i-1)(z+2)),w((i-1)(z+2)+1),\ldots,w(((i-1)(z+2)+z-1)\\}$. For
each $i$, $1\leq i\leq 5$, pebbles are placed at the nodes of $N_{i}(w)$ as
follows. For $1\leq a\leq z$, if the $a$-th bit of $\hat{\Gamma}$ is 1, then
place a pebble at the node $w((i-1)(z+2)+a-1)$ only if
$w((i-1)(z+2)+a-1)\not\in\\{s(0),s(1)\\}$. If $\ell\geq 8$, then place a
pebble at each of the nodes $v_{5},\ldots,v_{\ell-3}$. Fig. 2 shows pebble
placement in Case L-H.

Figure 2: Showing Pebble placement for Case L-H. Here the nodes that are used
for pebble placements may be in $L_{0}\cup L_{1}\cup L_{2}$.

Case L-L-H: The placement of pebbles in this case is similar to the placement
in Case L-H. The path coded in the neighbors of $w$ is a subpath of the path
$P$ starting from $s$. As before, depending on the position of the
$milestone_{2}$, different sequences of port numbers are coded in the
neighbors of $milestone_{1}$. Since $milestone_{1}\in L_{2}$ in this case,
$s(0)$, $s(1)$ may be connected to $milestone_{1}$. For this reason, as
before, the subpath is coded in five disjoint sets of neighbors of
$milestone_{1}$.

Formal description of placements of pebbles in this case in described below.
Let $milestone_{2}=v_{\ell}$. As per the definition of milestones, $\ell\geq
5$.

  1. 1.

$\left[\ell=5\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},v_{2},v_{3},v_{4},v_{5}$ and the corresponding sequence of port
numbers is $p_{0},p_{1},p_{2},p_{3},p_{4}$. Let $\Gamma^{\prime}=B_{0}\cdot
B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}$ and $\Gamma=11\cdot\Gamma^{\prime}$.

  2. 2.

$\left[\ell=6\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},v_{2},v_{3},v_{4},v_{5},v_{6}$ and the corresponding sequence of
port numbers is $p_{0},p_{1},p_{2},p_{3},p_{4},p_{5}$. Let
$\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}\cdot B_{5}$
and $\Gamma=10\cdot\Gamma^{\prime}$.

  3. 3.

$\left[\ell=7\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},v_{2},v_{3},v_{4},v_{5},v_{6},v_{7}$ and the corresponding
sequence of port numbers is $p_{0},p_{1},\ldots,p_{\ell}$. In this case, the
sequence of port numbers $p_{0},p_{1},p_{2},p_{3},p_{4},p_{5},p_{6}$ is coded.
Let $\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}\cdot
B_{5}\cdot B_{6}$ and $\Gamma=01\cdot\Gamma^{\prime}$.

  4. 4.

$\left[\ell\geq 8\right]$: Here the path from $s$ to $milestone_{2}$ is
$v_{0},v_{1},\ldots v_{\ell}$ and the corresponding sequence of port numbers
is $p_{0},p_{1},\ldots,p_{\ell}$. In this case, the sequence of port numbers
$p_{0},p_{1},p_{2},p_{3},p_{4},p_{\ell-3},p_{\ell-2},p_{\ell-1}$ is coded. Let
$\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}\cdot
B_{\ell-3}\cdot B_{\ell-2}\cdot B_{\ell-1}$ and
$\Gamma=00\cdot\Gamma^{\prime}$.

Let $\hat{\Gamma}$ be the transformed binary encoding of $\Gamma$ and $z$ is
the length of $\hat{\Gamma}$. Let $N_{i}(w)$, for $1\leq i\leq 5$, be the set
$z$ consecutive neighbors of $w$ starting from the node $w((i-1)(z+2))$. To be
specific,
$N_{i}(w)=\\{w((i-1)(z+2)),w((i-1)(z+2)+1),\ldots,w(((i-1)(z+2)+z-1)\\}$. For
each $i$, $1\leq i\leq 5$, pebbles are placed at the nodes of $N_{i}(w)$ as
follows. For $1\leq a\leq z$, if the $a$-th bit of $\hat{\Gamma}$ is 1, then
place a pebble at the node $w((i-1)(z+2)+a-1)$ only if
$w((i-1)(z+2)+a-1)\not\in\\{s(0),s(1)\\}$. If $\ell\geq 8$, then place a
pebble at each of the nodes $v_{5},\ldots,v_{\ell-3}$.

###### Remark 2.1

It can be noted that maximum of 8 port numbers must be coded in this case in
each of the five disjoint sets of neighbors of $milestone_{1}$. The
transformed binary representation of each port can be of at most
$2(1+\lfloor\log\Delta\rfloor)$ length. Also, two bits are used as marker to
represent the distance between first and second milestones. Hence in each set,
a string of length $16(1+\lfloor\log\Delta\rfloor)+2$ is coded. Therefore,
over all, among 5 sets, the nodes that are used to code the sequences of port
numbers is $80\lfloor\log\Delta\rfloor+90$. Also there are two zeros must be
coded in between two consecutive sets to show separations between them and at
the end at least 8 nodes kept blank (this is because if $s(1)$ appears in one
of the first 4 blank nodes after these 5 sets). Hence the degree of
$milestone_{1}$ must be at least $80\lfloor\log\Delta\rfloor+106$. Since every
milestone is heavy, and $\Delta\geq 2^{10}$ (for $\Delta\geq 2^{10}$,
$\Delta\geq 80\lfloor\log\Delta\rfloor+106$), therefore, such a coding can be
done in the neighbors of $milestone_{1}$.

Case L-L-L: This is the case where the two nodes $s(0)$ and $s(1)$ that are
used for markers are not connected to $milestone_{1}$ as $milestone_{1}\in
L_{j}$, for some $j\geq 3$. Hence, it is easy to code the paths in the
neighbors of $milestone_{1}$ like Case H. The only difference here is, the
subpath coded is a path starting from $v_{j-3}$. Depending on the position of
$milestone_{2}$, either the sequence of port number corresponding to the
entire path from $v_{j-3}$ to $milestone_{2}$ or the sequence
$p_{j-3},p_{j-2},p_{j-1},p_{j},p_{j+1},p_{j+2}$, and the last three ports
before $milestone_{2}$ are coded. For every light nodes starting from $v_{1}$
to $v_{j-3}$, a pebble is placed on these nodes that guides the agent towards
$milestone_{1}$. One more difficulty here is the case when
$v_{1}\in\\{s(0),s(1)\\}$, as we can not place a pebble in any of the nodes
$s(0),s(1)$, otherwise it is not possible to recognize the Case L-L-L. To
overcome this difficulty, we place a pebble at $s$, if $milestone_{1}\in
L_{3}$. Now, the agent, starting from $s$, first identify the Case L-L-L by
not seeing any pebbles in $s(0)$, and $s(1)$. If $s$ contains a pebble, the
agent learns that $milestone_{1}\in L_{3}$. It then explores all possible
paths of length 3 and finds the node with maximum degree. This node is
$milestone_{1}$. If no pebble is placed at $s$, and it finds any pebble at a
node $s(i)$, $i>1$, then it understands that $s(i)=v_{1}$. Else, if no pebble
is found at any of the nodes $s(2),s(3),\ldots$, and no pebble is present at
$s$, then it understands that $v_{1}\in\\{s(0),s(1)\\}$. In this case, the
agent first moves to $s(0)$, assuming it is the node $v_{1}$. If it finds a
neighbor of $v_{1}$, except $s$ that contains a pebble, then it moves to that
node (this must be the $v_{2}$). Else, it moves back to $s$ and then moves to
$s(1)$, assuming it as $v_{1}$. If it finds a neighbor of $v_{1}$, except $s$
that contains a pebble, then it moves to that node (this must be the node
$v_{2}$). If no pebble is found at any neighbor of $s(1)$ as well, then the
agent learns that $milestone_{1}\in L_{4}$. The agent explores all possible
paths of length 3 from $s(0)$ and explores all possible paths of length 3 from
$s(1)$ and finds the node with maximum degree. The agent moves to this node as
this is the node $milestone_{1}$. The coding in the neighbors of
$milestone_{1}$ is done in the same way as described for Case H.

The formal description of the pebble placement is as follows. Let $j$ be the
integer such that $w=milestone_{1}\in L_{j}$ and let $\ell$ be the integer
such that $milestone_{2}=v_{\ell}$.

  1. 1.

$\left[\ell-j=3\right]$: Here the path from $v_{j-3}$ to $milestone_{2}$ is
$v_{j-3},v_{j-2},v_{j-1},v_{j},$ $v_{j+1},v_{j+2},v_{j+3}$ and the
corresponding sequence of port numbers is $p_{j-3},$
$p_{j-2},p_{j-1},p_{j},p_{j+1},p_{j+2}$. Let $\Gamma^{\prime}=B_{j-3}\cdot
B_{j-2}\cdot B_{j-1}\cdot B_{j}\cdot B_{j+1}\cdot B_{j+2}$ and
$\Gamma=11\cdot\Gamma^{\prime}$.

  2. 2.

$\left[\ell-j=4\right]$: Here the path from $v_{j-3}$ to $milestone_{2}$ is
$v_{j-3},v_{j-2},v_{j-1},v_{j},$ $v_{j+1},$ $v_{j+2},v_{j+3},v_{j+4}$ and the
corresponding sequence of port numbers is
$p_{j-3},p_{j-2},p_{j-1},p_{j},p_{j+1},p_{j+2},p_{j+3}$. Let
$\Gamma^{\prime}=B_{j-3}\cdot B_{j-2}\cdot B_{j-1}\cdot B_{j}\cdot
B_{j+1}\cdot B_{j+2}\cdot B_{j+3}$ and $\Gamma=10\cdot\Gamma^{\prime}$.

  3. 3.

$\left[\ell-j=5\right]$: Here the path from $v_{j-3}$ to $milestone_{2}$ is
$v_{j-3},v_{j-2},v_{j-1},v_{j},$ $v_{j+1},v_{j+2},v_{j+3},v_{j+4},v_{j+5}$ and
the corresponding sequence of port numbers is
$p_{j-3},p_{j-2},p_{j-1},p_{j},p_{j+1},p_{j+2},p_{j+3},p_{j+4}$. Let
$\Gamma^{\prime}=B_{j-3}\cdot B_{j-2}\cdot B_{j-1}\cdot B_{j}\cdot
B_{j+1}\cdot B_{j+2}\cdot B_{j+3}\cdot B_{j+4}$ and
$\Gamma=01\cdot\Gamma^{\prime}$.

  4. 4.

$\left[\ell-j\geq 6\right]$: Here the path from $v_{j-3}$ to $milestone_{2}$
is $v_{j-3},v_{j-2}\ldots v_{\ell}$ and the corresponding sequence of port
numbers is $p_{j-3},p_{j-2},\ldots p_{\ell-1}$. In this case, the sequence of
port numbers $p_{j-3},p_{j-2},p_{j-1},p_{j},p_{j+1},p_{j+2},p_{j+3},$
$p_{\ell-3},p_{\ell-2},p_{\ell-1}$ is coded. Let $\Gamma^{\prime}=B_{j-3}\cdot
B_{j-2}\cdot B_{j-1}\cdot B_{j}\cdot B_{j+1}\cdot B_{j+2}\cdot B_{j+3}\cdot
B_{\ell-3}\cdot B_{\ell-2}\cdot B_{\ell-1}$ and
$\Gamma=00\cdot\Gamma^{\prime}$.

Let $\hat{\Gamma}$ be the transformed binary encoding of $\Gamma$ and let $z$
be the length of the string $\hat{\Gamma}$.

For $1\leq a\leq z$, place a pebble at $w(a-1)$ if the $a$-th bit of
$\hat{\Gamma}$ is 1. If $\ell-j\geq 7$, then place a pebble at each of the
nodes $v_{j+4},\ldots v_{\ell-3}$. Also, for $2\leq i\leq j-3$, place a pebble
at each of the node $v_{i}$. If $j=4$, place a pebble at $s$. If
$v_{1}\not\in\\{s(0),s(1)\\}$, then place a pebble at $v_{1}$.

Phase 3: Placing Pebbles to encode paths between other milestones

The coding of the paths between $milestone_{j}$ to $milestone_{j+1}$, for
$j\geq 2$ are done in the similar fashion as described in Case H. The only
difference here is the encoding is done in the neighbors of $milestone_{j}$
starting from $milestone_{j}(0)$. For the last milestone, the path from the
last milestone to the treasure is coded in the same way as described for the
other cases.

Let the total number of milestones be $y$. For $m=2,3,\ldots,y-1$, let $v_{j}$
be the node on $P$ such that $milestone_{m}=v_{j}$ and
$milestone_{m+1}=v_{\ell}$. For $m=y$, set $\ell=t$.

  1. 1.

$\ell-j\leq 3$ then $\ell\leq j+3$. The path from $v_{j}$ to $v_{\ell}$ is
$v_{j},v_{j+1}\ldots v_{\ell}$ and the corresponding sequence of port numbers
is $p_{j},p_{j+1},\ldots,p_{\ell-1}$. Let $\Gamma^{\prime}=B_{j}\cdot
B_{j+1}\cdots B_{\ell-1}$ and $\Gamma=11\cdot\Gamma^{\prime}$.

  2. 2.

$\ell-j=4$ then $\ell=j+4$. The path from $v_{j}$ to $v_{\ell}$ is
$v_{j},v_{j+1},v_{j+2},v_{j+3},v_{j+4}$ and the corresponding sequence of port
numbers is $p_{j},p_{j+1},p_{j+2},p_{j+2},p_{j+3}$. Let
$\Gamma^{\prime}=B_{j}\cdot B_{j+1}\cdot B_{j+2}\cdot B_{j+3}$ and
$\Gamma=10\cdot\Gamma^{\prime}$.

  3. 3.

$\ell-j=5$ then $\ell=j+5$. The path from $v_{j}$ to $v_{\ell}$ is
$v_{j},v_{j+1},v_{j+2},v_{j+3},v_{j+4},v_{j+5}$ and the corresponding sequence
of port numbers is $p_{j},p_{j+1},p_{j+2},p_{j+2},p_{j+3},p_{j+4}$. Let
$\Gamma^{\prime}=B_{j}\cdot B_{j+1}\cdot B_{j+2}\cdot B_{j+3}\cdot B_{j+4}$
and $\Gamma=10\cdot\Gamma^{\prime}$.

  4. 4.

If $\ell-j\geq 6$, and $\ell\neq t$ then let $\Gamma^{\prime}$ be the binary
representation of the sequence of port numbers
$p_{j},p_{j+1},p_{j+2},p_{\ell-3},p_{\ell-2},p_{\ell-1}$. If $\ell=t$ then
$\Gamma$ is the binary representation of the sequence of port numbers
$p_{j},p_{j+1},p_{j+2}$. $\Gamma=00\cdot\Gamma^{\prime}$.

For $1\leq a\leq z$, place a pebble at $w(a-1)$ if the $a$-th bit of $\Gamma$
is 1. If $\ell-j\geq 7$, then place a pebble at each of the nodes
$v_{j+4},\ldots v_{t-3}$. If $\ell=t$, then place a pebble at each of the
nodes $v_{t-2}$ and $v_{t-1}$.

  1. 1.

$\left[\ell=3\right]$: Here the path from $milestone_{1}$ to $milestone_{2}$
is $v_{0},v_{1},v_{2},v_{3}$ and the corresponding sequence of port numbers is
$p_{0},p_{1},p_{2}$. Let $\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}$ and
$\Gamma=11\cdot\Gamma^{\prime}$.

  2. 2.

$\left[\ell=4\right]$: Here the path from $milestone_{1}$ to $milestone_{2}$
is $v_{0},v_{1},v_{2},v_{3},v_{4}$ and the corresponding sequence of port
numbers is $p_{0},p_{1},p_{2},p_{3}$. Let $\Gamma^{\prime}=B_{0}\cdot
B_{1}\cdot B_{2}\cdot B_{3}$ and $\Gamma=10\cdot\Gamma^{\prime}$.

  3. 3.

$\left[\ell=5\right]$: Here the path from $milestone_{1}$ to $milestone_{2}$
is $v_{0},v_{1},v_{2},v_{3},v_{4},v_{5}$ and the corresponding sequence of
port numbers is $p_{0},p_{1},p_{2},p_{3},p_{4}$. Let
$\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{3}\cdot B_{4}$ and
$\Gamma=01\cdot\Gamma^{\prime}$.

  4. 4.

$\left[\ell\geq 6\right]$: Here the path from $milestone_{1}$ to
$milestone_{2}$ is $v_{0},v_{1},\ldots v_{\ell}$ and the corresponding
sequence of port numbers is $p_{0},p_{1},\ldots p_{\ell}$. As mentioned
earlier, the sequence of port numbers
$p_{0},p_{1},p_{2},p_{\ell-3},p_{\ell-2},p_{\ell-1}$ is coded in this case.
Let $\Gamma^{\prime}=B_{0}\cdot B_{1}\cdot B_{2}\cdot B_{\ell-3}\cdot
B_{\ell-2}\cdot B_{\ell-1}$ and $\Gamma=00\cdot\Gamma^{\prime}$.

Let $\hat{\Gamma}$ be the transformed binary encoding of $\Gamma$. Let $z$ be
the length of the string $\hat{\Gamma}$. For $1\leq i\leq z$, place a pebble
on $s(1+i)$, if the $i$-th bit of $\hat{\Gamma}$ is 1. If $\ell\geq 7$, then
place a pebble on each of the nodes $v_{4},\ldots v_{\ell-3}$.

####  2.0.2 Treasure Hunt by The Mobile Agent

The main idea behind the treasure hunt algorithm executed by the agent is to
move from one milestone to the next milestone until the treasure is found.
Initially, the agent is at the node $s$. The position of the first milestone
is learned by the agent by visiting the two neighbors $s(0)$ and $s(1)$ of
$s$. Based on whether a pebble is present in either of these nodes, the agent
determines the location of $milestone_{1}$ and then moves to the same.
According to the pebble placement strategy, the neighbors of every milestone
are used to code the path towards the next milestone. From a milestone, the
agent visits a set of its neighbors and decode the sequence of port numbers
corresponding to the path from the current milestone to the next milestone.
Using this information and identifying the pebbles placed at the light nodes
along the paths, the agent reaches to the next milestone. This process
continues until the treasure is found. The detail description of the treasure
hunt algorithm is give below.

The agent follows Algorithm 1 to find the treasure. Starting from the node
$s$, it first visits the two nodes $s(0)$ and $s(1)$. If pebbles are found at
both the nodes, then the agent follow Algorithm 2; If a pebble is found at
$s(0)$ but no pebble is found at $s(1)$, then the agent follow Algorithm 3; If
a pebble is found at $s(1)$ but no pebble is found at $s(0)$, then the agent
follows Algorithm 4, otherwise the agent follows Algorithm 5 if no pebbles are
found in either of these two nodes.

1

2Starting from $s$, the agent visits two nodes $s(0)$, and $s(1)$ one by one
and comes back to $s$.

3if  _Both the nodes $s(0)$, and $s(1)$ contains a pebble each_ then

4 Subroutine_H (Algorithm 2)

5else if  _$s(0)$ contains a pebble and $s(1)$ does not contain any pebble_
then

6 Subroutine_L-H (Algorithm 3)

7else if  _$s(0)$ does not contain any pebble and $s(1)$ contains a pebble_
then

8 Subroutine_L-L-H (Algorithm 4)

9else if  _Neither $s(0)$ nor $s(1)$ contains a pebble _ then

10 Subroutine_L-L-L (Algorithm 5)

Algorithm 1 TreasureHunt

If two pebbles are found at each of the nodes $s(0)$ and $s(1)$, the agent
learns that $s$ is heavy. According to Algorithm 2, the agent visits the nodes
$s(2),s(3),\ldots$ until it found two nodes $s(z+1)$ and $s(z+2)$ such that no
pebbles are found in both of these nodes. Let $\hat{\Gamma}=b_{2}b_{3}\ldots
b_{z}$ be the binary string such that $b_{i}=1$ if a pebble is found at
$s(i)$, else $b_{i}=0$. Let $\Gamma$ be the string obtained from
$\hat{\Gamma}$ by replacing each ‘11’ by ’1’ and each ‘10’ by 0 of
$\hat{\Gamma}$ from left to right, taking two bits a a time. The first two
bits of $\Gamma$ represents the distance of $milestone_{2}$ from $s$. The
agent, knowing the degree of $s$, compute $\alpha_{s}=1+\lfloor\log
deg(s)\rfloor$. Let $q_{0}$ be the integer that is represented by the
substring $\Gamma(3,4+\alpha_{s})$. The agent moves along the port $p$ to
reach the node $v_{1}$. Once it moves to $u_{1}$, it learns its degree and
computes $\alpha_{v_{1}}$. It then compute the integer $q_{1}$ that is coded
in the substring $\Gamma(5+\alpha_{s},6+\alpha_{s}+\alpha_{v_{1}})$. The agent
moves along the port $q_{1}$ to reach the node $v_{2}$. The agent continues to
move this way distances 3,4,5, if the first two bits represent the markers
‘11’,‘10’,‘01’, respectively to reach $milestone_{2}$. For the marker ‘00’
represented by $s(2)$ and $s(3)$, the agent moves distance 3 as per the above
strategy, to reach a node $v_{3}$. It then visits all the neighbors of $v_{3}$
and move to the neighbor that contains a pebble. This process continues until
for a node, none of its neighbors contains any pebble. In this case, the agent
retrieve the next three ports encoded in the rest of the substring of
$\Gamma$, one by one and moving to the respective node and move along three
edges to reach to $milestone_{2}$.

1

2$CurrentNode=s$.

3The agent visits the neighbors of $s$ starting from $s(2)$, in the increasing
order of the port number through which $s$ is connected to them until it finds
two consecutive neighbors where no pebbles are placed.

4Let $\hat{\Gamma}=b_{2}b_{3}\ldots b_{z}$ be the binary string where $b_{i}$
is 1 if a pebble is found at $s(i)$ and the last two nodes visited in the
previous step by the agent are $s(z+1)$ and $s(z+2)$.

5Let $\Gamma$ be the binary string obtained from $\hat{\Gamma}$ by replacing
every ‘11’ by a ‘1’ and every ‘10’ by a ‘0’ from left to right by taking two
bits at a time.

6$CurrentIndex=3$.

7$MinDistance=3$

8FindNextMilestone($b_{2},b_{3},\Gamma,MinDistance$) (Algorithm 7)

Progress($CurrentNode$) (Algorithm 8)

Algorithm 2 Subroutine_H

If a pebble is found in $s(0)$ but no pebble is found in $s(1)$, the agent
learns that $milestone_{1}\in L_{1}$. In this case, it executes
Subroutine_L-H. The agent visits all the neighbor of $s$ and finds the
neighbor $w$ with maximum degree. In case of tie, the agent moves to the node
with maximum degree to which $s$ is connected via smallest port number is .
This node $w$ is $milestone_{1}$. The agent, after moving to $w$ from $s$,
starts visiting all the neighbors of $w$ one by one until it finds four
consecutive neighbors $w(z),w(z+1)$, $w(z+2)$, and $w(z+3)$ none of which
contain any pebble. The agent construct the binary string
$\Gamma^{\prime}=b_{0}b_{1}\ldots b_{z-1}$, where $b_{i}=1$ if a pebble was
found at $w(i)$, else $b_{i}=0$. This string is split into substrings that are
separated by the substring ‘00’ and the agent computes the substring
$\hat{\Gamma}$ whose occurrence among these substrings is maximum. Let
$\Gamma$ be the string obtained from $\hat{\Gamma}$ by replacing each ‘11’ by
‘1’ and each ‘10’ by ‘0’ of $\hat{\Gamma}$ from left to right, taking two bits
a a time. The agent computes the ports one by one as described for Algorithm 2
and move towards the second milestone. The only difference here is after
computing $\Gamma$, the agent comes back to $s$ from $milestone_{1}$ and the
path coded at $\Gamma$ starts from $s$.

1 The agent visits all the neighbors of $s$ and let $w$ be the node that have
the maximum degree among all the neighbors of $s$. In case where multiple
nodes with maximum degree exists, let $w$ be the node to which $s$ is
connected via the smallest port number.

2The agent moves to $w$. Let $q$ be the incoming port at $w$ of the edge
$(s,w)$.

3The agent visits the neighbors of $w$ in the increasing order of the port
number through which $w$ is connected to them until it finds four consecutive
neighbors where no pebbles are placed.

4Go back to $s$ from $w$ using port number $q$. $CurrentNode=s$.

5Let ${\Gamma^{\prime}}=b_{0}b_{1}\ldots b_{z^{\prime}}$ be the binary string
where $b_{i}$ is 1 if a pebble is found at $w(i)$ and the last four nodes
visited in the previous step by the agent are
$w(z^{\prime}),w(z^{\prime}+1),w(z^{\prime}+2),w(z^{\prime}+3)$.

6Partition $\Gamma^{\prime}$ into substrings that are separated by two
consecutive zeros. Let $\hat{\Gamma}$ be the string that matches with most of
these substrings.

7Let $\Gamma$ be the string obtained from $\hat{\Gamma}$ by replacing every
‘11’ by ‘1’ and every ‘10’ by ‘0’ from left to right by taking two bits at a
time. Let $b$ and $b^{\prime}$ be the first two bits of $\Gamma$.

8$CurrentIndex=3$. $MinDistance=4$

9FindNextMilestone($b,b^{\prime},\Gamma,MinDistance$) (Algorithm 7)

Progress($CurrentNode$) (Algorithm 8)

Algorithm 3 Subroutine_L-H

If a pebble is found at $s(0)$ but no pebble at $s(1)$, the agent learns that
$milestone_{1}\in L_{2}$. In this case, the agent executes Subroutine_L-L-H
(Algorithm 4). From $s$, it explores all possible paths of length 2 from $s$
and moves to the maximum degree node in $L_{2}$ to which $s$ is connected
through the lexicographycally shortest path. After moving to $w$, the agent
computes the binary string $\Gamma$ in the same way as described in case of
Algorithm 3 and proceed towards the second milestone. Here, the string
$\Gamma$ that is computed by the agent, codes the path starting from $s$ and
the agent, after learning $\Gamma$, moves back to $s$ and moves forward
according to subpath coded in $\Gamma$ towards the second milestone.

1 The agent visits all the neighbors of $s$ and let $w$ be the node the
maximum degree node in $L_{2}$ to which $s$ is connected through the
lexicographycally shortest path.

2The agent moves to $w$.

3 The agent visits the neighbors of $w$ in the increasing order of the port
number through which $w$ is connected to them until it finds four consecutive
neighbors where no pebbles are placed.

4Go back to $s$.

5$CurrentNode=s$.

6Let $\Gamma^{\prime}=b_{0}b_{1}\ldots b_{z^{\prime}-1}$ be the binary string
where $b_{i}$ is 1 if a pebble is found at $w(i)$ and the last four nodes
visited in the previous step by the agent are
$w(z^{\prime}),w(z^{\prime}+1),w(z^{\prime}+2),w(z^{\prime}+3)$.

7Partition $\Gamma^{\prime}$ into substrings that are separated by consecutive
zeros. Let $\hat{\Gamma}$ be the string that matches with most of these
substrings.

8Let $\Gamma$ be the string obtained from $\hat{\Gamma}$ by replacing every
‘11’ by a ‘1’ and every ‘10’ by a ‘0’ of $\hat{\Gamma}$ by taking two bits at
a time from left to right. Let $b,b^{\prime}$ be the first two bits of
$\Gamma$, respectively.

9$MinDistance=5$. $CurrentIndex=3$

10FindNextMilestone($b,b^{\prime},\Gamma,MinDistance$) (Algorithm 7)

Progress($CurrentNode$) (Algorithm 8)

Algorithm 4 Subroutine_L-L-H

If no pebbles are found at both $s(0)$ and $s(1)$, the agent learns that
$milestone_{1}\in L_{j}$ for some $j\geq 3$. It then visits all the neighbors
of $s$ and identify the node $v_{1}$ by finding a neighbor with a pebble.
Here, as mentioned in the pebble placement algorithm, the problem occurs when
$v_{1}\in\\{s(0),s(1)\\}$, as these two nodes are already used as marker and
therefore no pebble can be placed here. In this case, the agent considers both
$s(0)$ and $s(1)$ as possible candidates for $v_{1}$.

Once $milestone_{2}$ is reached, the agent moves according to Algorithm 8.
Until the treasure is found, the agent, learn the sequence of port numbers
that leads towards the next milestone by visiting the neighbors of the current
milestone. Then following this sequence of port numbers and using the pebbles
placed on the light nodes, the agent moves to the next milestone. This process
continues until the treasure is found.

During the execution of the tresure hunt algorithm, the agent uses a set of
global variables, $CurrentNode$, $MinDistance$, and $CurrentIndex$. The
variable $CurrentNode$ denotes the node from which the current call of the
algorithms are executed. The $MinDistance$ variable stores the integers which
is the minimum number of ports that are coded in the neighbor of the current
milestone. The $CurrentIndex$ indicates the position of the binary string
(represents the sequence of port numbers towards the next milestone) from
which the coding of the port number along the shortest path from $CurrentNode$
starts.

The following lemmas ensure the correctness of the proposed algorithm.

1$CurrentNode=s$.

2Visit all the neighbors of $CurrentNode$.

3if  _Treasure is found_ then

4 Stop and terminate.

5if  _a pebble found at a node $v$_ then

6 Move to $v$. Set $CurrentNode=v$. Go to Step 5.

7else

8 if  _$CurrentNode\neq s$_ then

9 Visit all the paths from $CurrentNode$ of length 3. Let $w$ be the node of
maximum degree connected to $CurrentNode$ by the lexicographicaly shortest
path of length 3.

10 Move to $w$. Store the incoming ports of the path from $v$ to $w$ in a
stack.

11 else

12 if  _$s$ contains a pebble_ then

13 Go to Step 5.

14 else

15 Move to $s(0)$. Let $q$ be the port number of the edge $(s,s(0))$ at
$s(0)$. Visit all the neighbors of $s(0)$.

16 if  _a pebble is found at a neighbor $v$ of $s(0)$_ then

17 Move to $v$. Set $CurretNode=v$. Go to Step 5.

18 else

19 Return to $s$ using port $q$ from $s(0)$. Move to $s(1)$. Let $q^{\prime}$
be the port number of the edge $(s,s(1))$ at $s(1)$. Visit all the neighbors
of $s(1)$.

20 if  _a pebble is found at a neighbor $v$ of $s(1)$_ then

21 Move to $v$. Set $CurretNode=v$. Go to Step 5.

22 else

23 Move back to $s$. Go to Step 5.

24The agent visits the neighbors of $w$ in the increasing order of the port
number through which $w$ is connected to them until it finds two consecutive
neighbors where no pebbles are placed.

25Let $\hat{\Gamma}=b_{0}b_{1}\ldots b_{z-1}$ be the binary string where
$b_{i}$ is 1 if a pebble is found at the node $w(i)$ and the last two nodes
visited in the previous step by the agent are $w(z)$ and $w(z+1)$.

26Let $\Gamma$ be the string obtained from $\hat{\Gamma}$ by replacing every
‘11’ by a ‘1’ and every ‘10’ by a ‘0’ of $\hat{\Gamma}$ by taking two bits at
a time from left to right. Let $b,b^{\prime}$ be the first two bits of
$\Gamma$, respectively.

27Move back to $CurrentNode$ using the path stored in the stack.

28$CurrentIndex=3$, $MinDiatnace=6$.

29Algo FindNextMilestone($b,b^{\prime},\Gamma,MinDistance$)(Algorithm 7)

Progress($CurrentNode$) (Algorithm 8)

Algorithm 5 Subroutine_L-L-L

1 Let $p$ be the integer that is represented by the substring constructed from
$\Gamma(i,x)$.

2The agent move from the current node to the node $u$ to which the current
node is connected via port $p$.

3if  _Treasure found_ then

4 Stop and terminate.

5else

6 $CurrentNode=u$. $CurrentIndex=x+1$

Algorithm 6 Movement($i$,$x$, $\Gamma$)

1

2if  _$a=1$ and $b=1$_ then

3 for  _$j\leftarrow 1$ to $i$_ do

4 Movement($CurrentIndex$,$\alpha_{CurrentNode}$, $\Gamma$) (Algorithm 6)

5else

6 if  _$a=1$ and $b=0$_ then

7 for  _$j=1$ to $i+1$_ do

8 Movement($CurrentIndex$,$\alpha_{CurrentNode}$, $\Gamma$)

9 else

10 if  _$a=0$ and $b=1$_ then

11 for  _$j=1$ to $i+2$_ do

12 Movement($CurrentIndex$,$\alpha_{CurrentNode}$, $\Gamma$)

13 else

14 for  _$j=1$ to $i$_ do

15 Movement($CurrentIndex$,$\alpha_{CurrentNode}$, $\Gamma$)

16 while  _a pebble is found in some neighbor of $CurrentNode$_ do

17 Move to the neighbor $u$ of $CurrentNode$ that contains a pebble.
$CurrentNode=u$

18 for  _$i=1$ to 3_ do

19 Movement($CurrentIndex$,$\alpha_{CurrentNode}$, $\Gamma$)

20Progress($CurrentNode$) (Algorithm 8)

Algorithm 7 FindNextMilestone($a,b,\Gamma,i$)

1

2The agent visits the neighbors of $CurrentNode$ starting from
$CurrentNode(0)$, in the increasing order of the port number through which
$CurrentNode$ is connected to them until it finds two consecutive neighbors
where no pebbles are placed.

3Let $\hat{\Gamma}=b_{0}b_{1}\ldots b_{z}$ be the binary string where $b_{i}$
is 1 if a pebble is found at the node connected to $s$ through port $i$ and
the last two nodes visited in the previous step by the agent are $s(z+1)$ and
$s(z+2)$.

4Let $\Gamma$ be the binary string obtained from $\hat{\Gamma}$ by replacing
every 11 by a 1 and every 10 by a 0 from left to right by taking two bits at a
time.

5Let $b,b^{\prime}$ be the first two bits of $\Gamma$.

6$CurrentIndex=3$. $MinDistance=3$

7FindNextMilestone($b,b^{\prime},\Gamma,MinDistance$) (Algorithm 7)

Progress($CurrentNode$) (Algorithm 8)

Algorithm 8 Progress($CurrentNode$)

###### Lemma 2.1

In time $O((dist(s,milestone_{1})\log\Delta+\log^{3}\Delta))$, the agent
successfully reaches to $milestone_{1}$ starting from the node $s$.

Proof. We prove the lemma for each of the cases, Case H, Case L-H, Case L-L-H,
and Case L-L-L, one by one.

  * •

Case H: $s$ is itself $milestone_{1}$, and therefore the lemma is trivially
true.

  * •

Case L-H: $milestone_{1}\in L_{1}$. As per the definition of $milestone_{1}$,
here the maximum degree node in $L_{1}$ (in the case of tie, the node to which
$s$ is connected by the edge with minimum port number) is $milestone_{1}$.
According to the placement of pebbles, a pebble is placed at $s(0)$ and no
pebble is at $s(1)$. According to Algorithm 1, the agent, finding a pebble at
$s(0)$ and no pebble at $s(1)$ executes Algorithm 3. It moves to the node
whose degree is maximum among all neighbors of $s$ and to which $s$ is
connected via the smallest port number. Hence, the agent, following Algorithm
3, reaches $milestone_{1}$. Note that the time to reach $milestone_{1}$ is
$O(\log\Delta)$, as $s$ is a light node, and therefore, $deg(s)$ in
$O(\log\Delta)$.

  * •

Case L-L-H: $milestone_{1}\in L_{2}$. In this case, as per the definition of
$milestone_{1}$, the maximum degree node in $L_{2}$ (in the case of tie, the
node to which $s$ is connected by a path of length 2 which is
lexicographically shortest) is $milestone_{1}$. According to the placement of
pebbles, a pebble is placed at $s(1)$, and no pebble is at $s(0)$. According
to Algorithm 1, the agent, finding a pebble at $s(1)$ and no pebble at $s(0)$,
executes Algorithm 3. It moves to the node whose degree is maximum among all
nodes which are connected to $s$ by a path of length 2 (in the case of tie,
the node to which $s$ is connected by a path of length 2 which is
lexicographically shortest). Hence, the agent, by executing Algorithm 4,
reaches $milestone_{1}$. Note that the time to reach $milestone_{1}$ is
$O(\log^{2}\Delta)$, as $s$ and all the nodes in $L_{1}$ are light nodes, and
therefore the total number of paths from $s$ of length 2 is
$O(\log^{2}\Delta)$.

  * •

Case L-L-L: $milestone_{1}\in L_{j}$, for some $j\geq 3$. As per the pebble
placement strategy, no pebbles are placed on either of $s(0)$ and $s(1)$.
Further, if $milestone_{1}\in L_{3}$, then the node with maximum degree in
$L_{3}$ is chosen as $milestone_{1}$. No pebble is placed in any of the nodes
in $L_{1}$ and $L_{2}$. Now, after not founding any pebble at $s(0)$ and
$s(1)$, if there is a pebble in $s$, then the agent learns that
$milestone_{2}\in L_{3}$. According to Algorithm 5, the agent explores all
possible paths of length 3 and moves to the node with maximum degree (tie is
broken as earlier). This ensures that it reaches to $milestone_{1}$.

If $milestone_{1}\in L_{j}$, for $j\geq 3$, then a pebble is placed at each of
the nodes $v_{2},\ldots,v_{j-3}$ and a pebble is placed at $v_{1}$ if
$v_{1}\not\in\\{s(0),s(1)\\}$. As per the definition of $milestone_{1}$ in
this case, the node in $L_{j}$ with maximum degree and at a distance 3 from
$v_{j-3}$ is defined as $milestone_{1}$. According to the pebble placement
algorithm, no pebbles are placed at $s(0)$ and $s(1)$. If
$v_{1}\not\in\\{s(0),s(1)\\}$, then a pebble is placed at $v_{1}$. The agent,
according to Algorithm 5, starting from $s$ visits all the neighbor of $s$,
and moves to $v_{1}$, which is the node that contains a pebble. Then from
$v_{1}$, it moves to $v_{2}$, as this is the only neighbor of $v_{1}$ that
contains a pebble, and continue this process until it reaches to $v_{j-3}$,
none of whose neighbors contains any pebbles (except $v_{j-4}$ but this the
agent can detect by storing the incoming ports every time). Therefore, by Step
5 of Algorithm 5, the agent explores all possible paths of length 3 from
$v_{j-3}$ and moves to the node that have maximum degree at distance 3 from
$v_{j-3}$. Hence, the agent successfully reaches to $milestone_{1}$ in this
case as well. The only case remains to show is that when $milestone_{1}\in
L_{j}$, for $j\geq 3$ and $v_{1}\not\in\\{s(0),s(1)\\}$. In this case, both of
the nodes $s(0),s(1)$ are possible position for the node $v_{1}$ and the agent
explores as per the other case assuming $s(0)$ as $v_{1}$ once and then $s(1)$
as $v_{1}$ next. Hence, by a similar argument as mentioned in the previous
cases (Cases H, L-H, L-L-H), the agent reaches to $milestone_{1}$
successfully. Next, we compute the time taken by the agent from $s$ to
$milestone_{1}$. Note that each of the nodes $s,v_{1},v_{2},\ldots,v_{j-3}$
are light nodes in this case. Since, a pebble is placed at each of these nodes
and the agent moves to these nodes one by one by exploring all the neighbors
and finding the pebble, the total time taken by the agent is
$O((j-3)\log\Delta)$, i.e, $O(dist(s,milestone_{1})\log\Delta)$. Once the
agent reaches to $v_{j-3}$, it finds the $milestone_{1}$ by exploring all
possible paths of length 3, that will take $O(\log^{3})\Delta$-time.
Therefore, the total time taken to reach $milestone_{1}$ is
$O((dist(s,milestone_{1})\log\Delta+\log^{3}\Delta))$.

In the next two lemmas, we prove that from $milestone_{1}$ the agent reaches
to $milestone_{2}$ for each of the different cases. The first lemma proves
this for the Case H and Case L-L-L and the second lemma proves this for the
Case L-H and Case L-L-H.

###### Lemma 2.2

The agent successfully reaches to $milestone_{2}$ form $milestone_{1}$ for
Case H and Case L-L-L.

Proof. The proofs for Case H and Case L-L-L are similar. The only difference
is that the path coded in the neighbors of $milestone_{1}$ starts from
$milestone_{1}$ itself in Case H, whereas, in Case L-L-L, the path coded in
the neighbors of $v_{j}=milestone_{1}$ starts from $v_{j-3}$. We first
describe the proof for Case H.

In Case H, recall that $s$ is heavy and therefore $milestone_{1}=s$. Suppose
that $milestone_{2}\in L_{j}$. According to Algorithm 2, the agent, visits all
the neighbors of $s$ one by one, starting from $s(2)$, in the increasing order
of the port number until it finds two consecutive neighbors without pebbles.
It then computes the binary string $\hat{\Gamma}=b_{2}\cdots b_{z}$, where
$b_{i}=1$ if a pebble is found in $s(i)$, else $b_{i}=0$. Then the string
$\Gamma$ is constructed from $\hat{\Gamma}$ by replacing every ‘11’ by a ‘1’
and every ‘10’ by ‘0’ from left to right of $\hat{\Gamma}$ by taking two bits
at a time. As per the pebble placement algorithm, $\Gamma$ represents a
sequence of port numbers that leads towards $milestone_{2}$. To be specific,
depending on the position of $milestone_{2}$, the following two cases may
happen.

  * •

$\left[milestone_{2}\in L_{j},~{}j\leq 6\right]$: In this case, the sequence
$p_{0},p_{1},\ldots,p_{j}$ is encoded using the pebbles, i.e.,
$\Gamma^{\prime}$ is the binary representation of the sequence
$p_{0},p_{1},\ldots,p_{j}$, where $\Gamma=b_{2}b_{3}\cdot\Gamma^{\prime}$ and
one of $b_{2}$ and $b_{3}$ is 1. The agent identify this by finding at least
one pebble at $s(2)$ or $s(3)$. After learning $\Gamma^{\prime}$, and knowing
the degree of $s$, the agent compute the substring containing first
$1+\lfloor\log degree(s)\rfloor$ bits and decode the integer $p_{0}$. After
decoding $p_{0}$, it moves to the node $v_{1}$ from $s$ by taking the port
$p_{0}$. As soon as the agent reaches $v_{1}$, it learns the degree of $v_{1}$
and then decode the integer $p_{1}$ which is decoded in the next
$1+\lfloor\log deg(v_{1})\rfloor$ bits of $\Gamma^{\prime}$. Following this
port from $v_{1}$, the agent reaches $v_{2}$ and learns the degree of $v_{2}$.
Continuing this way, the agent decodes the integers $p_{2},\ldots,p_{j-1}$ one
by one and finally reaches to node $v_{j}$ which is $milestone_{2}$.

  * •

$\left[milestone_{2}\in L_{j},\text{for~{}}j>6\right]$: Here the sequence
$p_{0},p_{1},p_{2},p_{j-3},p_{j-2},p_{j-1}$ is coded in $\Gamma^{\prime}$.
According to the pebble placement algorithm, there are no pebble at $s(2)$ and
$s(3)$. The agent identify this case by not finding any pebbles both at $s(2)$
and $s(3)$. According to Algorithm 2, the agent set $CurrentIndex=4$ and
$Mindistance=3$, and call the subroutine
FindNextMilestone$(0,0,\Gamma,MinDistance)$. Since $b_{2}=0$ and $b_{3}=0$,
according to Steps 7 \- 7 of FindNextMilestone, the agent decodes the port
numbers $p_{0},p_{1},p_{2}$ one by one and then reaches $v_{1}$, $v_{2}$, and
$v_{3}$ respectively. Once it reaches $v_{3}$, it starts exploring all the
neighbors of $CurrentNode$ and moves to the node that contains a pebble and
update $CurrentNode$ (Ref. Step 7). It continues to move in this way until it
finds no pebble in the neighborhood of $CurrentNode$ (except the node from
where it reaches $CurrentNode$). According to the pebble placement algorithm,
this situation arises when $v_{j-3}$ is the $CurrentNode$. From $v_{j-3}$, the
agent decodes $p_{j-3}$, from $\Gamma$, and moves to $v_{j-2}$, and decodes
$p_{j-2}$ from $\Gamma$ and moves to $v_{j-1}$, and then finally, decodes
$p_{j-1}$ and reach to $v_{j}$ which is $milestone_{2}$.

In Case L-L-L, the proof is similar as in Case H. After learning the sequence
$\Gamma$ which is encoded in the neighbors of $milestone_{1}$, the agent
returns back to $v_{j-3}$ and move one by one along $P$ by decoding the port
numbers $p_{j-3},p_{j-2},\ldots$, to reach $milestone_{2}$. In case
$milestone_{2}$ more than 6 distance apart from $v_{j}$, the agent first moves
to $v_{j+3}$ from $v_{j-3}$ by decoding first 6 ports one by one. After that
it’s movement is guided by the light nodes from $v_{j+4}$ to $v_{\ell-3}$,
where $milestone_{2}=v_{\ell}$. Once it reaches to $v_{\ell-3}$, the agent
finds no pebble in the neighborhood of $CurrentNode$ which is $v_{\ell-3}$
(except the node from where it reaches $CurrentNode$, i.e., $v_{\ell-4}$).
From $v_{\ell-3}$, the agent decodes $p_{\ell-3}$ from $\Gamma$, and moves to
$v_{\ell-2}$, and decodes $p_{\ell-2}$ from $\Gamma$ and moves to
$v_{\ell-1}$, and then finally, decodes $p_{\ell-1}$ from $\Gamma$ and reaches
to $v_{\ell}$ which is $milestone_{2}$.

###### Lemma 2.3

The agent successfully reaches to $milestone_{2}$ from $milestone_{1}$ for
Case L-H and Case L-L-H.

Proof. We prove the lemma for Case L-H. The proof for Case L-L-H is similar.

According to Lemma 2.1, the agent successfully reaches to the node
$w=milestone_{1}$. After reaching $milestone_{1}$, the agent computes the
binary string $\hat{\Gamma}$ (Ref. Step 3 of Algorithm 3). According to the
pebble placement algorithm, the sequence of port numbers corresponding to the
path from $s$ to $milestone_{2}$ is coded in 5 disjoint sets of neighbors of
$milestone_{1}$. We show that the agent correctly computes this encoding of
the path. In this case, a pebble is placed in $s(0)$ and no pebble is at
$s(1)$. Consider the following cases.

  * •

$s(0),s(1)\not\in\\{w(0),w(1),\ldots,w(5z+11)\\}$. In this case, $\Gamma$ is
the string that is equals to
$\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}$. Hence,
the string separated by ‘00’ which occurs most of the time is $\hat{\Gamma}$.
Hence, $\hat{\Gamma}$ in learned correctly by the agent in this case.

  * •

$s(0)\in N_{i}(w)$ and $s(1)\in N_{j}(w)$ for some $i,j\leq 5$. In this case,
the string $\hat{\Gamma}$ can not be correctly coded in the sets $N_{i}(w)$
and $N_{j}(w)$. To be more specific, one bit of the string encoded in
$N_{i}(w)$ and one bit of the string encoded in $N_{j}(w)$ may differ from
$\hat{\Gamma}$. (in case $i=j$, at most two bits can differ from $\Gamma$).
Therefore, In this case, the string $\Gamma^{\prime}$ which is computed by the
agent is the string that is equals to
$\Gamma_{1}00\Gamma_{2}00\Gamma_{3}00\Gamma_{4}00\Gamma_{5}$, where
$\Gamma_{i},\Gamma_{j}\neq\hat{\Gamma}$ and $\Gamma_{k}=\hat{\Gamma}$, for
$k\in\\{1,2,3,4,5\\}\setminus\\{i,j\\}$. It can be seen that $\hat{\Gamma}$ is
the most occurring substring separated by 00, and hence $\hat{\Gamma}$ is
correctly computed in this case.

  * •

$s(0)\in\\{w(i(z+2)-2),w(i(z+2)-1)$, for some $1\leq i\leq 4$, i.e, $s(0)$ (it
contains a pebble in this case) is a node that are left blank to represent two
consecutive zeros. Without loss of generality, suppose that $s(0)=w(z)$. In
this case $\Gamma^{\prime}$ is the string that looks like
$\hat{\Gamma}10\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}$. The
substrings that are separated by ‘00’ are $\Gamma_{1}$, and three substrings
equals to $\hat{\Gamma}$, where $\Gamma_{1}=\hat{\Gamma}10\hat{\Gamma}$.
Hence, $\hat{\Gamma}$ is the substring that is the most occurred substring and
therefore, $\hat{\Gamma}$ is correctly computed in this case as well.

  * •

$s(0)\in\\{w(5z+8),w(5z+9),w(5z+10),w(5z+11)\\}$. This is the case where the
node $s(0)$ appears as one of the four nodes after all the nodes of the five
sets $N_{i}(w)$. Here, the string $\Gamma^{\prime}$ looks like
$\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}00\hat{\Gamma}00{\Gamma_{1}}$ where
$\Gamma_{1}$ is a substring whose one of the four end bits corresponds to
$s(0)$. In this case as well, $\hat{\Gamma}$ is the most occurred string and
therefore the agent correctly learn $\hat{\Gamma}$.

Once the agent correctly learn $\hat{\Gamma}$, it computes $\Gamma$ by
replacing every ‘11’ by ‘1’ and every ‘10’ by ‘0’. If the first two bits of
$\Gamma$ is the substring ‘11’, or ‘10’, or ‘01’ then the agent learns that
$milestone_{2}$ is at 4 or 5, or 6 distance apart, respectively from $s$. The
agent returns back to $s$ from $w$ and move one edge at a time by decoding the
integers $p_{0}$, $p_{1},p_{2},\ldots,p_{\ell}$, for $\ell=4,5,6$ and then
successfully reaches to $milestone_{2}$. If the first two bits of $\Gamma$ is
the substring ‘00’, then agent learns that $milestone_{2}$ is at least 7
distance apart. The agent returns back to $s$ from $w$, and move one edge at a
time by decoding the integers $p_{0}$, $p_{1}$, $p_{2}$, and $p_{3}$, to reach
the node $v_{4}$. According to the pebble placement algorithm, if
$milestone_{2}\in L_{\ell}$, then no pebble is placed on any node in
$L_{\ell-2}$, and a pebble is placed at each of the nodes
$v_{5},\ldots,v_{\ell-3}$. The agent, from $v_{4}$ moves to $v_{5}$, then to
$v_{6}$, and so on until the node $v_{\ell-3}$ by moving to the neighbor of
the current node that contains a pebble. Once it reaches to $v_{\ell-3}$, it
can not find any other neighbor of $v_{\ell-3}$, other than $v_{\ell-4}$ that
contains a pebble. The agent learns in this point that it reaches to
$v_{\ell-3}$ and then it starts decoding the rest three port numbers one by
one and following them, to finally reach to $milestone_{2}$.

###### Lemma 2.4

After reaching $milestone_{j}$, for some $j\geq 2$, the agent successfully
either reaches to $milestone_{j+1}$, if exists, or finds the treasure.

Proof. We prove this lemma using induction. By Lemma 2.1, the agent
successfully reaches $milestone_{1}$. To prove the base case, we prove that
from $milestone_{1}$, it reaches to $milestone_{2}$ successfully.

Let $y$ be the total number of milestones. Suppose that the agent successfully
reached to $milestone_{j}$ for $j<y$. It then executes Algorithm 8 (subroutine
Progress) according to which it visits all the neighbors of $CurrentNode$
which is $milestone_{j}$ and compute the string $\Gamma^{\prime}$. As per the
pebble placement algorithm, $\Gamma^{\prime}$ represents a sequence of port
numbers that leads towards $milestone_{j+1}$. To be specific, depending on the
position of $milestone_{j+1}$, the following cases may happen.

  * •

If $milestone_{j}\in L_{\ell}$ and $milestone_{j+1}\in L_{\ell^{\prime}}$,
such that $\ell^{\prime}-\ell\leq 6$. In this case, the sequence
$p_{\ell},p_{\ell+1},\ldots,p_{\ell^{\prime}-1}$ is encoded in the neighbors
of, i.e., $\Gamma^{\prime}$ is the binary representation of the sequence
$p_{0},p_{1},\ldots,p_{j}$, where $\Gamma=b_{1}b_{1}\cdot\Gamma^{\prime}$ and
one of $b_{1}$ and $b_{2}$ is 1. The agent identify this by finding at least
one pebbles at $milestone_{j}(0)$ and $milestone_{j}(1)$. After learning
$\Gamma^{\prime}$, and knowing the degree of $milestone_{j}$, the agent
compute the substring containing first $1+\lfloor\log degree(s)\rfloor$ bits
and decode the integer $p_{\ell}$. After decoding $p_{\ell}$, it moves to the
node $v_{\ell+1}$ from $v_{\ell}$ by taking the port $p_{\ell}$. As soon as
the agent reaches $v_{\ell+1}$, it learns the degree of $v_{\ell+1}$ and then
decode the integer $p_{\ell+1}$ which is decoded in the next $1+\lfloor\log
deg(v_{\ell+1})\rfloor$ bits of $\Gamma^{\prime}$. Following this port from
$v_{\ell+1}$, the agent reaches $v_{\ell+2}$ and learns the degree of
$v_{\ell+2}$. Continuing in this way the agent finally reaches to node
$v_{\ell^{\prime}}$ which is $milestone_{2}$.

  * •

If $milestone_{j+1}\in L_{\ell^{\prime}}$, for $\ell^{\prime}-\ell>6$. In this
case, the sequence $p_{\ell}$, $p_{\ell+1}$, $p_{\ell+2}$,
$p_{\ell^{\prime}-3}$, $p_{\ell^{\prime}-2}$, $p_{\ell^{\prime}-1}$ is coded
in $\Gamma^{\prime}$. According to the pebble placement algorithm, there are
no pebble at $milestone_{j}(0)$ and $milestone_{j}(1)$. The agent identify
this case by not finding any pebbles at $milestone_{j}(0)$, and
$milestone_{j}(1)$. According to Algorithm 8, the agent set $CurrentIndex=3$
and $Mindistance=3$, and call FindNextMilestone$(0,0,\Gamma,MinDistance)$
(Algorithm 7). According to Step 7\- 7 of Algorithm 7, the agent decodes the
port numbers $p_{\ell},p_{\ell+1},p_{\ell+2}$ one by one and then reaches
$v_{\ell+1}$, $v_{\ell+2}$, and $v_{\ell+3}$, respectively. Once it reaches
$v_{\ell+3}$, it starts exploring all the neighbors of $CurrentNode$ and moves
to the node that contains a pebble and update $CurrentNode$ (Ref. Step 7 of
Algorithm 7). It continues to move in this way until it finds no pebble in the
neighborhood of $CurrentNode$ (except the node from where it reaches
$CurrentNode$). According to the pebble placement algorithm, this situation
arises when $v_{\ell^{\prime}-3}$ is the $CurrentNode$. From
$v_{\ell^{\prime}-3}$, the agent decodes $p_{\ell^{\prime}-3}$ from $\Gamma$,
and moves to $v_{\ell^{\prime}-2}$, and decodes $p_{\ell^{\prime}-2}$ from
$\Gamma$ and moves to $v_{\ell^{\prime}-1}$, and then finally, decodes
$p_{\ell^{\prime}-1}$ and reach to $v_{\ell^{\prime}}$ which is
$milestone_{j+1}$.

Hence using the induction hypothesis, the agent reaches to $milestone_{y}$. In
the neighbors of $milestone_{y}$, the path from $milestone_{y}$ to the
treasure is coded. If the distance of $t$ from $milestone_{y}$ is $\leq 6$,
then the entire path to the treasure is coded in the neighbors of
$milestone_{y}$. The agent, in a similar fashion as described earlier, learn
this path by decoding the port numbers one by and one and finally finds the
treasure. In case the path to the treasure is of length at least 7, then only
first three ports from $milestone_{1}$ are coded in the neighbors of
$milestone_{y}$. The agent from $milestone_{y}=v_{\ell}$ reached to the node
$v_{\ell+3}$, and then it starts exploring all the neighbors of
$CurrentNode=v_{\ell+3}$ and moves to the node that contains a pebble and
update $CurrentNode$ of Algorithm 7). It continues to move this way and
finally finds the treasure and stop.

We now present our final result in the following theorem.

###### Theorem 2.1

The agent finds the treasure in $O(D\log\Delta+\log^{3}\Delta)$-time.

Proof. There are $O(\log\Delta)$ pebbles that are placed in the neighbors of
each milestone and at most one pebble is placed on each of the light nodes on
$P$. Since there can be at most $\frac{D}{3}$ milestones and $O(D)$ light
nodes, hence the total number of pebbles used is $O(D\log\Delta)$.

The agent visits $O(\log\Delta)$ neighbors of each milestone and all the
neighbors of each light node on $P$. The total time taken to find the treasure
from $milestone_{1}$ is $D(\log\Delta)$. Also, by Lemma 2.1, the agent reaches
to $milestone_{1}$ in
$O(dist(s,milestone_{1})\log\Delta+\log^{3}\Delta)$-time. Since
$dist(s,milestone_{1})\leq D$, the time for treasure hunt is
$O(D\log\Delta+\log^{3}\Delta)$.

##  3 Lower bound

In this section, we show a a lower bound $\Omega(D\log\Delta)$ for time of
treasure hunt. To be specific, we construct a class of instances of treasure
hunt such that if the time for treasure hunt is ‘short’, then any algorithm
using any number of pebbles can not find the treasure within this short time
for some instances.

Let $T$ be a complete tree of height $D$ where the degree of the root $r$ and
each internal node is $\Delta$. There are $\Delta\cdot(\Delta-1)^{D-1}$ leaves
in $T$. Let $p=\Delta\cdot(\Delta-1)^{D-1}$ and $u_{1},\ldots,u_{p}$ be the
leaves of $T$ in lexicographical ordering of the shortest path from the root
$r$. For $1\leq i\leq p$, we construct an input $B_{i}$ as follows. The tree
$T$ is taken as the input graph, $r$ as the starting point of the agent, and
$u_{i}$ as the position of the treasure. Let ${\cal B}$ be the set of all
inputs $B_{i}$, $1\leq i\leq p$.

Suppose that there exists an algorithm ${\cal A}$ that can solve the treasure
hunt in time $t$ for all graphs of maximum degree $\Delta$ and $D$ being the
distance between the initial position of the agent and the treasure. The
movement of the agent according to ${\cal A}$ can be viewed as a sequence of
port numbers $p_{1},p_{2},\ldots,p_{t}$, where the values of the port numbers
depend only on the placement of pebbles. To be specific, at any time
$t^{\prime}\leq t$, the agent takes a port $p$ if a pebble is placed in the
current vertex, else it takes a port $p^{\prime}$. Note that $p$ and
$p^{\prime}$ may be the same port. In other words, depending on the placement
of the pebbles, at any step, the agent can take one of the two possible ports,
and therefore total at most $2^{{t}}$ possible sequences of port numbers the
agent may follow from its initial position to find the treasure. This
observation is formally proved in the following lemma.

###### Lemma 3.1

For any treasure hunt algorithm ${\cal A}$ taking $t$-time, there are at most
$2^{t}$ possible sequences of port numbers the agent may follow for the
treasure hunt.

Proof. We use induction to prove the above statement. Consider the execution
of the algorithm for $t=1$, i.e., the agent traverse exactly one edge. There
are two possible cases. If no pebble is placed at the starting position of the
agent, the agent must take some specified port $p$, following ${\cal A}$. If a
pebble is placed at the starting node, then the agent must take some specified
port $q$ (may be $p=q$). Hence, there are at most one of the two different
sequences of port numbers can be followed by the agent, according to ${\cal
A}$. Suppose that, the statement is true for any $t^{\prime}<t$, i.e., there
are at most $2^{t^{\prime}}$ possible different sequences of port numbers, one
which the agent might follow depending on the position of the pebbles. Let $Q$
be a sequence of port numbers among these $2^{t^{\prime}}$ different
sequences. Let $v$ be the position of the agent after following $Q$ starting
from the initial position. As argued, in the case for $t=1$, there are two
possible port numbers one of which the agent can take in time $t^{\prime}+1$
depending on whether a pebble is placed or not at the current node $v$. Since
this statement is true for every possible sequences of port numbers of length
$t^{\prime}$, this implies that there are at most $2\times
2^{t^{\prime}}=2^{t^{\prime}+1}$ many possible sequences of port numbers of
length $t^{\prime}+1$. Therefore, the statement is followed by induction.

The following theorem proves the lower bound result.

###### Theorem 3.1

There exists a graph $G$ of maximum degree $\Delta~{}(\geq 2)$ and diameter
$D~{}(\geq 3)$ such that any deterministic algorithm must require
$\Omega(D\log\Delta)$-time for the treasure hunt irrespective of the number of
pebbles placed on the nodes of $G$.

Proof. Suppose that there exists an algorithm that solves the treasure hunt in
time at most $\frac{D\log(\Delta-1)}{2}$ for the class of inputs ${\cal B}$.
By Lemma 3.1, there are at most
$2^{\frac{D\log(\Delta-1)}{2}}=(\Delta-1)^{\frac{D}{2}}$ different possible
sequences of port numbers the agent can follows. Since $|{\cal
B}|=\Delta(\Delta-1)^{D-1}$, therefore, by the Pigeon hole principle, there
exist at least $(\Delta-1)^{\frac{D}{2}}$ inputs in ${\cal B}$ for which the
agent follows the same sequence of port numbers. Since
$\frac{D\log(\Delta-1)}{2}<(\Delta-1)^{\frac{D}{2}}$, for $\Delta\geq 3$, it
is not possible to reach the treasure for $(\Delta-1)^{\frac{D}{2}}$ many
inputs using the same sequence of port numbers of length
$\frac{D\log(\Delta-1)}{2}$. This contradicts the fact that ${\cal A}$ solves
the treasure hunt in time at most $\frac{D\log(\Delta-1)}{2}$ for the class of
inputs ${\cal B}$. Hence the theorem follows.

##  4 Conclusion

We propose an algorithm for the treasure hunt problem that finds the treasure
in an anonymous graph in $O(D\log\Delta+\log^{3}\Delta)$-time. We also prove a
lower bound of $\Omega(D\log\Delta)$. Clearly, there is a small gap between
the upper and lower bounds, however, the gap is smaller than any polynomial of
$\Delta$. A natural open question is to find tight upper and lower bounds for
the problem. Another interesting problem is to study trade-off between number
of pebble and time for treasure hunt in anonymous networks.

## References

  * [1] Steve Alpern and Shmuel Gal.  The theory of search games and rendezvous, volume 55 of International series in operations research and management science.  2003\.
  * [2] Ricardo A. Baeza-Yates, Joseph C. Culberson, and Gregory J. E. Rawlins.  Searching in the plane.  Inf. Comput., 106(2):234–252, 1993.
  * [3] A. Beck and D.J. Newman.  Yet more on the linear search problem.  Israel J. Math, 8:419 – 429, 1970.
  * [4] Lucas Boczkowski, Amos Korman, and Yoav Rodeh.  Searching a tree with permanently noisy advice.  In ESA, pages 54:1–54:13, 2018.
  * [5] A. Bonato and R.J. Nowakowski.  The Game of Cops and Robbers on Graphs, American Mathematical Society, 2011.
  * [6] Sébastien Bouchard, Yoann Dieudonné, Arnaud Labourel, and Andrzej Pelc.  Almost-optimal deterministic treasure hunt in arbitrary graphs.  CoRR, abs/2010.14916, 2020.
  * [7] Sébastien Bouchard, Yoann Dieudonné, Andrzej Pelc, and Franck Petit.  Deterministic treasure hunt in the plane with angular hints.  Algorithmica, 82(11):3250–3281, 2020.
  * [8] Timothy H. Chung, Geoffrey A. Hollinger, and Volkan Isler.  Search and pursuit-evasion in mobile robotics - A survey.  Auton. Robots, 31(4):299–316, 2011.
  * [9] Erik D. Demaine, SÃ¡ndor P. Fekete, and Shmuel Gal.  Online searching with turn cost.  Theoretical Computer Science, 361(2):342 – 355, 2006.
  * [10] Yann Disser, Jan Hackfeld, and Max Klimm.  Tight bounds for undirected graph exploration with pebbles and multiple agents.  J. ACM, 66(6):40:1–40:41, 2019.
  * [11] Yuval Emek, Tobias Langner, David Stolz, Jara Uitto, and Roger Wattenhofer.  How many ants does it take to find the food?  Theoretical Computer Science, 608:255 – 267, 2015.
  * [12] G. M. Fricke, J. P. Hecker, A. D. Griego, L. T. Tran, and M. E. Moses.  A distributed deterministic spiral search algorithm for swarms.  In 2016 IEEE/RSJ (IROS), pages 4430–4436, 2016.
  * [13] Barun Gorain and Andrzej Pelc.  Deterministic graph exploration with advice.  ACM Trans. Algorithms, 15(1):8:1–8:17, 2019.
  * [14] Artur J. and Jakub Lopuszanski.  On the two-dimensional cow search problem.  Information Processing Letters, 109(11):543 – 547, 2009.
  * [15] Ming-Yang Kao, John H. Reif, and Stephen R. Tate.  Searching in an unknown environment: An optimal randomized algorithm for the cow-path problem.  Inf. Comput., 131(1):63–79, 1996.
  * [16] Elmar Langetepe.  Searching for an axis-parallel shoreline.  Theoretical Computer Science, 447:85 – 99, 2012.
  * [17] Tobias Langner, Barbara Keller, Jara Uitto, and Roger Wattenhofer.  Overcoming obstacles with ants.  In OPODIS, pages 9:1–9:17, 2015.
  * [18] Avery Miller and Andrzej Pelc.  Tradeoffs between cost and information for rendezvous and treasure hunt.  In OPODIS, pages 263–276, 2014.
  * [19] Andrzej Pelc and Ram Narayan Yadav.  Information complexity of treasure hunt in geometric terrains.  CoRR, abs/1811.06823, 2018.
  * [20] Andrzej Pelc and Ram Narayan Yadav.  Cost vs. information tradeoffs for treasure hunt in the plane.  CoRR, abs/1902.06090, 2019.
  * [21] K. Spieser and E. Frazzoli.  The cow-path game: A competitive vehicle routing problem.  In 2012 IEEE (CDC), pages 6513–6520, 2012.
  * [22] Amnon Ta-Shma and Uri Zwick.  Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences.  ACM Trans. Algorithms, 10(3):12:1–12:15, 2014.