Sébastien Bouchard
email: sebastien.bouchard@u-bordeaux.fr

Yoann Dieudonné
email: yoann.dieudonne@u-picardie.fr

Arnaud Labourel
email: arnaud.labourel@lis-lab.fr

Andrzej Pelc
email: pelc@uqo.ca.

Almost-Optimal Deterministic Treasure Hunt in Arbitrary Graphs

Keywords: treasure hunt, graph, mobile agent

A mobile agent navigating along edges of a simple connected graph, either finite or countably infinite, has to find an inert target (treasure) hidden in one of the nodes. This task is known as treasure hunt. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure. Awerbuch, Betke, Rivest and Singh [3] considered graph exploration and treasure hunt for finite graphs in a restricted model where the agent has a fuel tank that can be replenished only at the starting node s. The size of the tank is B = 2(1 + α)r, for some positive real constant α, where r, called the radius of the graph, is the maximum distance from s to any other node. The tank of size B allows the agent to make at most B edge traversals between two consecutive visits at node s.

 with the same complexity. Thus we refute the above twenty-year-old conjecture. We observe that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and thus our algorithms are also almost optimal.

1 Introduction

The background

A mobile agent has to find an inert target (treasure) in some environment that can be a network modeled by a graph or a terrain in the plane. This task, known as treasure hunt, has important applications when the environment is dangerous for humans. When a miner is lost in a contaminated mine, it may have to be found by a robot, and the length of the robot's trajectory should be as short as possible, in order to minimize rescuing time. In this example, a graph models the corridors of the mine with nodes representing crossings. Another application of treasure hunt in graphs is searching for a data item in a communication network modeled by a graph.

The models and the problem

We consider a simple connected undirected locally finite graph G = (V G , E G ), i.e., a graph with nodes of finite degrees. Such a graph can be either finite or countably infinite. A mobile agent (robot) starts at a node s of G, called the source node, and moves along its edges. The maximum distance of any node from s is denoted by r and called the radius of the graph (the radius of countably infinite graphs is infinite). We make the same assumption as in [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] that the agent has unbounded memory and can recognize already visited nodes and traversed edges. This is formalized as follows. Nodes of G have distinct labels that are positive integers. Each edge has ports at both of its extremities. Ports corresponding to edges incident to a node of degree δ are numbered 0, 1, . . . , δ -1 in an arbitrary way. At the beginning, the agent situated at node s sees its degree. The agent executes a deterministic algorithm: at each step, it selects a port number on the basis of currently available information, and traverses the corresponding edge. When the agent enters the adjacent node, it learns its label, its degree, and the incoming port number.

Each node of V G will be identified with its label, and each edge of E G will be identified as the quadruple (v, w, p, q), where v < w are labels of the edge extremities, p is its port number at node v and q is its port number at node w.

The above simple model will be called unrestricted. However, some authors imposed additional restrictions, in the case when the graph is finite. The authors of [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] used a restriction of moves of the agent that we will call the fuel-restricted model. They assumed that the agent has a fuel tank that can be replenished only at the starting node s of the agent. The size of the tank is B = 2(1 + α)r, for some positive real constant α, where r is the radius of the graph. The tank of size B allows the agent to make at most B edge traversals between two consecutive visits at node s. The restriction used in [START_REF] Duncan | Optimal constrained graph exploration[END_REF] was of a different kind. We will call it the rope-restricted model. It was assumed in [START_REF] Duncan | Optimal constrained graph exploration[END_REF] that the agent is tethered, i.e., attached to s by a rope that it unwinds by a length 1 with every forward edge traversal and rewinds by a length of 1 with every backward edge traversal. The rope is infinitely extendible but has to satisfy the following constraint: the segment of the rope unwinded by the agent must never be longer than L = (1 + α)r, for some positive real constant α. Hence the agent is forced to match every forward edge traversal of an edge with a backward edge traversal, rewinding the rope, in a first-in last-out stack order.

The task of treasure hunt, in any of the above three models, is defined as follows. An adversary hides the treasure in some node of the underlying graph G. The agent has no a priori knowledge of the graph, of the location of the treasure or of the initial distance to it, and has to find the treasure. The cost of a treasure hunt algorithm is the worst-case number of edge traversals performed by the agent until finding the treasure.

In order to state our problem we need the notion of a ball. Given a non-negative integer k, a graph G, and a node u, the ball B k (G, u) is defined as the subgraph K = (V K , E K ) of G, where V K is the set of all nodes at distance at most k from u in G, and E K is the set of all edges of G whose at least one extremity is at distance smaller than k from u in G. (Thus B k (G, u) is the subgraph of G induced by nodes at distance at most k without edges joining nodes at distance exactly k from u in G). The number of edges in ball B k (G, s), where s is the source node, will be denoted by e(k, G). Whenever the graph G is clear from the context, we will write e(k) instead of e(k, G).

The main problem considered in this paper is inspired by the following conjecture of Awerbuch, Betke, Rivest and Singh [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF], formulated for their fuel-restricted model: Is it possible (we conjecture not) to find a treasure in time nearly linear in the number of those vertices and edges whose distance to the source is less than or equal to that of the treasure? 1

Our results

Our main result refutes the above twenty-year-old conjecture. Let d be any integer such that 1 < d ≤ r, where r is the radius of the underlying graph G. We first design a deterministic treasure hunt algorithm working in the unrestricted model and always finding a treasure located at distance at most d from the source node, at cost O(e(d) log d). We then show how to modify this algorithm to work in the fuel-restricted and rope-restricted models with the same complexity. Since d ≤ e(d), the cost of our algorithms differs from e(d) only by a logarithmic factor, and hence it is nearly linear in e(d), contrary to the conjecture. Due to the ignorance of the agent concerning the graph in which it operates, no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs (cf. Proposition 2.1) and thus our algorithms are also almost optimal. The main difficulty is to design the algorithm for the unrestricted model. This algorithm is then suitably modified for each of the two restricted models.

Solving the problem of treasure hunt at a cost quasi-linear in e(d) required to respect two fundamental principles, whose joint implementation seemed precarious in the light of the existing literature.

The first one is a prudence principle. It consists in never getting "for too long" beyond the unknown distance d in order to guarantee a cost that depends on e(d). This can be ideally achieved by emulating BFS. However, since in such an emulation the agent must physically move from one node to the next, it may be forced to traverse Ω(e(d) 2 ) edges before finding the treasure, in some graphs. In particular, this could be the case when G is an infinite line.

The second principle is what we could call an efficiency principle. It consists in getting a cost that is asymptotically close to the number of edges of the subgraph that has been explored till finding the treasure, if the treasure is far away. This can be ideally achieved using the treasure hunt algorithm of [START_REF] Duncan | Optimal constrained graph exploration[END_REF], the cost of which is linear in the number of edges of the explored subgraph. However, using this algorithm, the agent may go for too long beyond the unknown distance d and consequently the cost of treasure hunt could not be upper bounded by any function of e(d). The key challenge overcome by our work was combining these two principles within the same algorithm. It is precisely the combination of prudence with efficiency that finally made possible the design of an almost-optimal treasure hunt algorithm.

Related work

The task of treasure hunt, i.e., finding an inert target hidden in some environment, has been studied for over fifty years [START_REF] Beck | On the linear search problem[END_REF][START_REF] Beck | Yet more on the linear search problem[END_REF][START_REF] Bellman | An optimal search problem[END_REF]. The environment where the target is hidden may be a graph or a plane, and the search may be deterministic or randomized. The book [START_REF] Alpern | The Theory of Search Games and Rendezvous[END_REF] surveys both treasure hunt and the related rendezvous problem, where the target and the searching agent are both mobile and they cooperate to meet. This book is concerned mostly with randomized search strategies. In [START_REF] Miller | Tradeoffs between cost and information for rendezvous and treasure hunt[END_REF][START_REF] Ta-Shma | Deterministic rendezvous, treasure hunts and strongly universal exploration sequences[END_REF] the authors studied relations between treasure hunt and rendezvous in graphs. The authors of [START_REF] Baeza-Yates | Searching the plane[END_REF] studied the task of treasure hunt on the line and in the grid, and initiated the study of the task of searching for an unknown line in the plane. This research was continued, e.g., in [START_REF] Jez | On the two-dimensional cow search problem[END_REF][START_REF] Langetepe | Searching for an axis-parallel shoreline[END_REF].

Several papers considered treasure hunt in the plane, see surveys [START_REF]Search Games: A Review, Search Theory: A Game Theoretic Perspective[END_REF][START_REF] Ghosh | Online algorithms for searching and exploration in the plane[END_REF]. In [START_REF] Langetepe | On the Optimality of Spiral Search[END_REF], the author designs an optimal algorithm to sweep the plane in order to locate an unknown fixed target, where locating means getting the agent originating at point O to a point P such that the target is in the segment OP . In [START_REF] Fricke | A Distributed Deterministic Spiral Search Algorithm for Swarms[END_REF], the authors generalized the search problem in the plane to the case of several searchers. Efficient treasure hunt in the plane, under complete ignorance of the searching agent, was studied in [START_REF] Pelc | Reaching a target in the plane with no information[END_REF]. Treasure hunt on the line (called the cow-path problem [START_REF] Kao | Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem[END_REF]) has been also generalized to the environment consisting of multiple rays originating at a single point [START_REF] Angelopoulos | Infinite linear programming and online searching with turn cost[END_REF][START_REF] Demaine | Online searching with turn cost[END_REF][START_REF] Lopez-Ortiz | The ultimate strategy to search on m rays?[END_REF][START_REF] Schuierer | Lower bounds in on-line geometric searching[END_REF].

In [START_REF] Fleischer | Competitive Online Approximation of the Optimal Search Ratio[END_REF], the authors considered treasure hunt in several classes of graphs including trees. Treasure hunt in trees was studied in [START_REF] Dasgupta | Agent searching in a tree and the optimality of iterative deepening[END_REF][START_REF] Dasgupta | A Correction to "Agent Searching in a Tree and the Optimality of Iterative Deepening[END_REF][START_REF] Kirkpatrick | Competitive search in symmetric trees[END_REF]. In [START_REF] Dasgupta | Agent searching in a tree and the optimality of iterative deepening[END_REF][START_REF] Dasgupta | A Correction to "Agent Searching in a Tree and the Optimality of Iterative Deepening[END_REF], the authors considered complete b-ary trees, and in [START_REF] Kirkpatrick | Competitive search in symmetric trees[END_REF], treasure hunt was studied in symmetric trees, with possibly multiple treasures.

In [START_REF] Komm | Treasure hunt with advice[END_REF][START_REF] Miller | Tradeoffs between cost and information for rendezvous and treasure hunt[END_REF], treasure hunt in graphs was considered under the advice paradigm, where a given number of bits of advice can be given to the agent, and the issue is to minimize this number of bits. The impact of different types of knowledge on the efficiency of the treasure hunt problem restricted to symmetric trees was studied in [START_REF] Kirkpatrick | Competitive search in symmetric trees[END_REF].

The two papers closest to the present work are [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF][START_REF] Duncan | Optimal constrained graph exploration[END_REF]. Both of them are mainly interested in exploration of finite unknown graphs but they both get interesting corollaries for the treasure hunt problem. [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] adopts the fuel-restricted model and [START_REF] Duncan | Optimal constrained graph exploration[END_REF] adopts the rope-restricted model. In [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF], the authors get a treasure hunt algorithm working at cost O(E + V 1+o (1) ), where E (resp. V ) is the number of edges (resp. nodes) in a ball B ∆ (G, s), with ∆ ≤ d + o(d), if the treasure is at distance at most d from the starting node of the agent. Since e(∆) may be a lot larger than e(d), this does not permit to bound the cost of the algorithm by any function of e(d). This impossibility may be the reason for their conjecture that we refute in this paper. In [START_REF] Duncan | Optimal constrained graph exploration[END_REF], the authors design, for any constant 0 < α < 1, a treasure hunt algorithm whose cost is linear in e((1 + α)d). Again, since e((1 + α)d) may be much larger than e(d), this does not permit to bound the cost of the algorithm by any function of e(d).

Preliminaries

In this section we introduce some conventions, definitions and procedures that will be used to describe and analyze our algorithm.

Consider any graph H

= (V H , E H ) ⊆ G.
If H is finite, its size i.e., its number of edges is denoted by |H|. A graph is said to be empty if it contains no node. In the rest of this section, we assume that H is not empty.

Let u and v be two (not necessarily distinct) nodes of H. We say that a sequence of i integers (x 1 , x 2 , . . . , x i ) is a path (of length i) in H from node u to v iff (1) i = 0 and u = v, or (2) there exists an edge e in H between node u and a node w of H such that the port number of edge e at node u is x 1 and (x 2 , . . . , x i ) is a path from node w to v in H. The lexicocraphically smallest shortest path from node u to v in H, if any, is denoted by P H (u, v), and the length of this path is denoted by |P H (u, v)|. The distance between u and v in H is denoted by d H (u, v) and is equal to

|P H (u, v)| if P H (u, v) exists, ∞ otherwise.
If H is finite and connected, the eccentricity H (u) of node u is defined as max w∈V H d H (u, w). The degree of u in H will be denoted by deg H (u), or simply by deg(u) if H = G. We say that node u is incomplete

(resp. complete) in H if deg H (u) < deg(u) (resp. deg H (u) = deg(u)).
We also say that a port p is free at node u in H, if p ≤ deg(u) -1 and there is no edge (u, * , p, * ) or ( * , u, * , p) in E H .

We will often need to handle subgraphs of G through union and intersection operations. More precisely, given two subgraphs H = (V H , E H ) and H = (V H , E H ) of G, the union of (resp. the intersection of) H and H is denoted by H H (resp. H H ) and is equal to

(V H ∪ V H , E H ∪ E H ) (resp. (V H ∩ V H , E H ∩ E H )).
We define the boundary of a ball B f (G, s), where s is the source node, as the set of nodes u satisfying the following condition: u is a node of B f (G, s) and for each neighbor

v of u in B f (G, s), d B f (G,s) (s, v) ≤ d B f (G,s) (s, u).
To design our algorithm, we will also make use of three basic routines presented below. The first routine is MoveTo(H, v). Assuming that the agent currently occupies a node w of H and P H (w, v) exists, this routine moves the agent from node w to node v by following path P H (w, v). The second routine is IncompleteNodes(v, H, l) where l is a positive integer. This routine returns the set of all nodes w of H such that d H (v, w) ≤ l and w is incomplete in H. The third routine is Nodes(S), where S is a finite set of finite subgraphs of G. This routine returns the union of all nodes in all subgraphs from S.

Given an execution E of a series of instructions, the cost of E is the number of edge traversals performed by the agent during E.

We will use the following convention. The agent will sometimes need to use Depth First Search traversal of graphs (not performed physically, but performed as a computation in the memory of the agent). Such a traversal depends on the order in which edges incident to a given node are traversed for the first time. We fix this order as the increasing order of port numbers at the given node. In this way the traversal is unambiguous, and we call it DFS.

We end this section with the following straightforward observation implying that no treasure hunt algorithm can beat cost Θ(e(d)) for all graphs and hence our treasure hunt algorithm is almost optimal2 . This observation holds in all three considered models: unrestricted, fuel-restricted and rope-restricted. In fact, the proposition shows that graphs G for which the cost of treasure hunt is at least Θ(e(d)) can be found for any density of edges in the ball B d (G, s). Let x be the first step when all nodes of H are visited, assuming that the treasure has not been found before. Let y be the number of untraversed edges of H at step x. There are two cases. If y < 2 then the adversary puts the treasure at the last-discovered node of H and the proposition is satisfied by graph H itself. Hence we may assume that y ≥ 2. Let e 1 , ..., e y be the edges of H untraversed by step x, and let H i , for i = 1, . . . , y, be the graph H with a midpoint added on edge e i . Note that none of the edges e i can be an element of the set X because this would contradict the fact that node a d has been visited by step x. Consequently, the radius of each graph H i is d. The set of nodes of B d (H i , s) is the set of nodes of B d (H, s) augmented by the midpoint added on edge e i , and we have e(d, H i ) = e(d, H) + 1. Thus, for all i, B d (H i , s) has Θ(m) nodes and Θ(x) edges. In this case the adversary will put the treasure at one of the added midpoints and claim that the actual graph is the corresponding graph H i . Below we show how to choose the index i. Since the treasure is not placed at any node of H, the execution of A until step x is the same in graphs H, H 1 ,...,H y . In order to find the treasure placed at the added node of some of the graphs H i , algorithm A must take the port corresponding to edge e i at one of its extremities. If it does not find a midpoint inserted in e i , i.e., if the actual graph is not H i , algorithm A must take the port corresponding to some other edge e j at one of its extremities, in order to find the treasure situated at the added midpoint of e j , if the actual graph were H j , and so on. Let e f be the last of the edges e i examined in this way. Suppose that the actual graph G is H f and that the adversary places the treasure at the midpoint of e f . Hence the cost of finding the treasure in the graph G = H f is at least e(d, H) -y + y = e(d, H) ≥ e(d, G) -1. This concludes the proof.

Intuition

The purpose of this section is to sketch an intuitive overview of our algorithm that allows to find the treasure at an almost-optimal cost in the unrestricted model. To this end and to simplify the discussion, we will assume that the underlying graph G is countably infinite with nodes of finite degrees. We will rely on the notion of largest explored ball. By "largest explored ball", at a given phase of treasure hunt, we mean the ball B f (G, s) where f is the largest integer such that each edge of B f (G, s) has been traversed at least once. This largest integer f is the radius of the largest explored ball.

At a high level, our algorithm works in phases i = 1, 2, 3, . . . and immediately stops as soon as the treasure is found. At the beginning of phase i, the agent is located at node s and the radius of the largest explored ball is equal to f i . The goal for the agent is to terminate the phase at node s while satisfying at least one of the following three conditions unless, of course, the treasure has been found before.

• Condition 1. The agent has entirely explored ball B f i +1 (G, s), e(f i + 1) ≥ 2e(f i ) and the cost of the phase is O(e(f i + 1)).

• Condition 2. The agent has entirely explored ball B 2f i (G, s), f i ≥ 1 and the cost of the phase is O(e(f i )).

• Condition 3. The agent has entirely explored ball B f i +k (G, s) for some positive integer k, e(f i + k + 1) ≥ 2e(f i ), f i ≥ 2, and the cost of the phase is O(e(f i ) log f i ).

Actually, the conditions we really seek to meet in our algorithm are a little more intricate than those presented above, because we needed stronger technical requirements to show Theorem 6.1, which refutes the conjecture of Awerbuch, Betke, Rivest and Singh [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF]. However, this would add an unnecessary level of complexity to understand the intuition, hence we omit these technical details here.

Before seeing how we implement our strategy, let us briefly examine why it permits us to get a cost quasi-linear in e(d). Since f 1 = 0 and the radius of the largest explored ball increases by at least one during each phase in which the treasure is not found, the agent necessarily finds the treasure by the end of some phase λ ≤ d, and f i < f λ < d for every 1 ≤ i < λ. During each phase satisfying Condition 1, the size of the largest explored ball at least doubles, which means that the total cost of these phases is upper bounded by twice the worst-case cost of the last phase satisfying Condition 1 i.e., O(e(f λ + 1)). Concerning the phases fulfilling Condition 2, their number is at most O(log(f λ + 1)) and the cost of each of them cannot be more than O(e(f λ )), which implies that their total cost is O(e(f λ ) log(f λ + 1)). It remains to consider the case of the phases satisfying Condition 3. Given such a phase i, we have the guarantee that the size of the largest explored ball at least doubles between the beginning of phase i and the end of phase i + 1, provided phase i + 1 exists and is not prematurely interrupted by the discovery of the treasure. Indeed, at the end of phase i, the agent has at least entirely explored ball B f i +k (G, s) for some positive integer k and e(f i + k + 1) ≥ 2e(f i ), while at the end of the (not prematurely interrupted) phase i + 1 the agent has at least entirely explored ball B f i+1 +1 (G, s) with f i+1 ≥ f i + k. Using this, it can be shown that the total cost of the phases satisfying Condition 3 is at most four times the worst-case cost of the last phase satisfying this condition i.e., O(e(f λ ) log(f λ + 1)). Given that the last phase λ can be viewed as a truncated phase that should have normally satisfied one of the three conditions, our sketch of analysis leads to the conclusion that the cost incurred by the agent till the discovery of the treasure is in O(e(f λ + 1) log(f λ + 1)), which is O(e(d) log d) and is in line with our expectations.

Having justified the pertinence of such a strategy, we can turn our attention to its implementation.

To do so, we need to introduce a technical building block, called GlobalExpansion(l, m) to which we will go back at the end of this section to give additional details. Always executed from the source node s, it is a function that returns a boolean and whose two input parameters are positive integers except m that may be sometimes equal to the special symbol ⊥. Assuming that B f (G, s) is the largest explored ball, the execution of GlobalExpansion(l, ⊥) permits the agent to traverse all the edges of B f +l (G, s) that are outside of B f (G, s) before coming back to node s. Under the same assumption, the execution of GlobalExpansion(l, m), when m is a positive integer, consists for the agent in acting as if m was ⊥ but with the following extra requirement: as soon as more than m distinct edges outside of B f (G, s) have been traversed during the execution of the function, the agent backtracks to node s and aborts this execution. If m is ⊥ or at least large enough to avoid an aborted execution, the agent ends up exploring B f +l (G, s) and the function returns true. Otherwise, the function returns false. It should be stressed that all of this is made while guaranteeing two properties. The first one is that the agent is always in B f +2l-1 (G, s) during the execution of GlobalExpansion(l, m). The second is that the cost of the execution of GlobalExpansion(l, m) is O(e(f + 2l -1)) (resp. O(min{e(f ) + m, e(f + 2l -1)})) when m =⊥ (resp. m =⊥). Both these properties will turn out to be crucial to ensure a proper design of the phases. Finally, even if by chance the agent could explore a larger ball, we will assume for the ease of our intuitive explanations that B f +l (G, s) (resp. B f (G, s)) is the largest ball explored by the agent at the end of GlobalExpansion(l, m) in the case where the returned value is true (resp. false).

Let us consider a phase i of our algorithm and, in order not to burden the text with a lot of "unless the treasure is found", let us assume that the treasure will not be found by the end of it. Phase i is made of at most three successive attempts, each of them aiming at fulfilling at least one of the three conditions described earlier, with the help of our building block. In the first attempt, the agent executes GlobalExpansion(1, ⊥) from node s, the cost of which is O(e(f i + 1)). At the end of this execution, the agent is at node s and B f i +1 (G, s) has been entirely explored by the agent. If e(f i + 1) ≥ 2e(f i ) or f i ≤ 1, the first attempt is a success as Condition 1 or Condition 2 is verified, and the agent directly switches to phase i + 1. Otherwise, the attempt is a failure, but we can nonetheless observe that the cost incurred because of the attempt is just O(e(f i )) because e(f i + 1) < 2e(f i ).

If the first attempt has failed, the agent starts the second attempt of phase i that consists of an execution of function GlobalExpansion(f i -1, e(f i )). The hope here is to expand by a distance of f i -1 the radius of the largest explored ball, which is B f i +1 (G, s). According to the properties of GlobalExpansion and the fact that e(f i + 1) < 2e(f i ), the cost of this execution, and thus of the second attempt, is O(e(f i )). If GlobalExpansion(f i -1, e(f i )) returns true, then at the end of the second attempt, the radius of the largest explored ball is 2f i . Hence, the cost of the first two attempts being equal to O(e(f i )) and f i being at least 2, Condition 2 is satisfied and the agent starts phase i + 1 without making the third attempt.

On the other hand, if GlobalExpansion(f i -1, e(f i )) returns false, it is a different story. Indeed, the largest explored ball is still only B f i +1 (G, s) and we cannot ensure the fulfillment of Condition 1 or Condition 2. This is exactly where Condition 3 comes into the picture. In order to remedy the failures of the two previous attempts, the agent will start a third and last attempt which consists of a dichotomic process that is described in Algorithm 1. At the end of this process, Condition 3 is guaranteed to be satisfied.

Algorithm 1: Third attempt

1 f loor := f i + 1; ceil := 3f i -2; l := ceil-f loor 2 ; 2 while l ≥ 1 and |B f loor (G, s)| < 2e(f i ) do 3 success := GlobalExpansion(l, e(f i )); 4 if success = true then 5 f loor := f loor + l; l := ceil-f loor 2 ; 6 else 7 ceil := f loor + 2l -1; l := l 2 ;
In order to better understand why we can get such a guarantee, let us take a look at the properties that are satisfied during the third attempt and at its end.

Since the execution of GlobalExpansion(f i -1, e(f i )) returned false, the agent has explored at least e(f i ) distinct edges outside of ball B f i +1 (G, s) during the second attempt. Moreover, during this execution, the agent was always in B 3f i -2 (G, s) according to the properties of GlobalExpansion.

As a result, in view of line 1 of Algorithm 1, we necessarily have the following feature before the execution of the while loop of Algorithm 1: B f loor (G, s) is the largest explored ball and e(ceil) ≥ 2e(f i ). Actually, by carefully examining the pseudocode of the while loop and using again the properties of GlobalExpansion, it can be inductively proven that this feature is a loop invariant.

Alone, this loop invariant is not enough to bring the sought guarantee, but as highlighted below, it is of precious help to do the job.

The number of iterations of the while loop can be shown to be O(log f i ). Furthermore, at the beginning of each iteration, B f loor (G, s) has size smaller than 2e(f i ) in view of the condition of the while loop, and is the largest explored ball in view of the loop invariant. Hence, according to the cost property of GlobalExpansion, each execution of GlobalExpansion(l, e(f i )) costs at most O(e(f i )) like the previous two attempts, which gives a total cost of O(e(f i ) log f i ) of the whole phase. This corresponds exactly to the target value of Condition 3. Along with this, at the end of the while loop, the size of B f loor (G, s) is at least 2e(f i ), or l < 1. In the first case, we immediately have e(f loor + 1) ≥ 2e(f i ), while in the second case it can be shown that ceil ≤ f loor + 1. This, combined with the fact that e(ceil) is always at least 2e(f i ) (by the loop invariant) and the fact that f loor is always at least f i +1, allows us to show the last missing piece of the puzzle, which is precisely this: when Algorithm 1 terminates, ball

B f i +k (G, s) is entirely explored and e(f i + k + 1) ≥ 2e(f i ) for some integer k ≥ 1.
To conclude with the intuitive explanations, let us give, as promised, some more insight concerning the building block GlobalExpansion(l, m). At first glance, one might think that GlobalExpansion could be directly derived from the exploration algorithm CFX(v, r, α) of [START_REF] Duncan | Optimal constrained graph exploration[END_REF], which permits to explore

a ball B r (G, v) at a cost of O |B (1+α)r (G,v)| α
for any given real α > 0 (this corresponds to a cost of O e((1+α)r) α when v = s) provided αr ≥ 1. Indeed, the task of GlobalExpansion(l, m) that consists in expanding the radius f of the largest explored ball by a distance l in the case where m is appropriately set, can be done with CFX(s, f + l, α). However, in this case we want the cost of this expansion to be O(e(f + 2l -1)), which is an important property of our strategy. This cannot be guaranteed using CFX(s, f +l, α) because, in order to get a cost depending on e(f +2l -1), we would have to set α to a value lower than l-1 f +l , which cannot lead to a cost that is linear in e(f + 2l -1), as l-1 f +l can be arbitrarily small. True, during the design we could have been "less demanding" about some of the properties of GlobalExpansion(l, m), but not significantly enough to permit the use of CFX(s, f + l, α) without spoiling the validity or the cost complexity of our strategy. Another solution that may come to mind would be to apply CFX(v, l, α) from each node v located on the boundary of the largest explored ball B f (G, s). Visiting each node of the boundary can be done in O(e(f )). Hence, this solution looks attractive because by setting α to 1 2 or less (which overcomes the above problem of the arbitrarily small value) and provided the zones explored by the different executions of CFX do not overlap, we would get a cost that is linear in e(f + 2l -1). The bad news is that there may be overlaps. Of course, some overlaps can be easily avoided, especially those appearing within B f (G, v), but some others cannot without running the risk of missing some nodes of B f +l (G, s) that are outside of B f (G, s). These "necessary overlaps" may be pernicious and may occur in a way that prevents us from guaranteeing a cost of O(e(f + 2l -1)).

So, what did we do? Although it was not possible to use CFX as a black box, we managed to tailor GlobalExpansion by adapting to our needs an elegant algorithmic technique used in CFX. Through a set of judiciously pruned trees spanning some already explored area, it allowed us to satisfy the desired cost property of GlobalExpansion by controlling and amortizing efficiently the number of times the same edges are traversed. The technique in question is detailed in the next section that presents the pseudocode of our treasure hunt algorithm.

Algorithm

Solving the treasure hunt problem in the unrestricted model can be done by executing Algorithm TreasureHunt(x) described below in Algorithm 2 and by interrupting it as soon as the treasure is found. The input parameter x is a positive real constant. It is a technical ingredient that will have an impact on the maximal distance at which the agent can be from node s. In our present context, parameter x does not really matter and it can be fixed as any positive real constant. In fact, it will show its full significance in Section 6 that is dedicated to the same problem in restricted models: there, we will reuse TreasureHunt(x) in a context where x will have to be carefully chosen. The variable M in line 2 of Algorithm 2 is a global variable that will always correspond to some explored subgraph of G. For this reason, it will recurrently appear in most of the pseudocodes of the functions described thereafter.

Algorithm 2: TreasureHunt(x)

1 v := the current node; 2 M := ({v}, ∅); /* M is a global variable */ 3 repeat 4 Search(x);
As the reader can see, the execution of Algorithm TreasureHunt(x) essentially consists of a series of executions of procedure Search(x), whose pseudocode is described in Algorithm 3: these executions correspond to what we called "phases" in our intuitive explanations of Section 3. Procedure Search(x) should be seen as the organizer of our solution. At the beginning of each call to Search(x), M is some explored ball B f (G, s) and the goal of the call is to make this ball grow while satisfying some conditions. These conditions, whose simplified version we gave at the beginning of Section 3, are formally described in Lemma 5.4. 11

M := B f loor (M, v); 12 i := i + 1;
Although there are some technical differences, we can discern, throughout the lines of Algorithm 3, the three attempts outlined in Section 3 that rely on function GlobalExpansion. Roughly speaking, line 3 of Algorithm 3 relates to the first attempt, the first iteration of the while loop of Algorithm 3 relates to the second attempt, and the other iterations relate to the third attempt.

The pseudocode of function GlobalExpansion(l, m) is given by Algorithm 4. It has primarily the same specifications as those given in Section 3 except that we did not implement the case where m =⊥ and l ≥ 2 as it was not necessary for our purpose. Hence, the function precisely handles the case where l = 1 and m =⊥, and the case where l ≥ 1 and m =⊥. The general scheme of the function is as follows. At the beginning, the agent knows a ball B f (G, s) that is stored in variable M and the objective is to expand the radius of this ball by a distance l, without exploring more than m edges outside of B f (G, s), if m =⊥. To do this, the agent visits the nodes L [START_REF] Alpern | The Theory of Search Games and Rendezvous[END_REF], L [START_REF] Angelopoulos | Infinite linear programming and online searching with turn cost[END_REF], . . . (stored in the array L) of the boundary of B f (G, s) and executes from these nodes function CDFS (described in Algorithm 5 and whose name stands for Constrained DFS) or function LocalExpansion (described in Algorithm 6) depending on the initial values of l and m. Each of these executions, which starts and ends at the same node, locally contributes to the global expansion of the ball. In the case where m =⊥, variable b of Algorithm 4 is updated with the return value of the two aforementioned functions, and corresponds at each stage to the remaining number of new edges the agent is authorized to traverse outside of B f (G, s). If b becomes negative before the end of the while loop of Algorithm 4, the objective of expansion is simply not reached. Note that, in order to avoid that the moves from one node of the boundary of B f (G, s) to the next get too costly, they are made according to a precise order that results from the definition of L given in line 2 of Algorithm 4. Note that in the particular case where l = 1 and m =⊥ in Algorithm 4, the second argument of each call to CDFS is always set to the degree of the node from which the function is executed (cf. line 9 of Algorithm 4) in order to ensure that this node becomes complete in M at the end of the call. To see the algorithmic technique in question at work, let us focus on an iteration I of the first while loop of Algorithm 6 occuring in LE i . This iteration starts at node L[i] and we will show in Section 5 that at the beginning of I, we necessarily have the following properties.

• T is a set of node disjoint trees that are all subgraphs of M.

• For each tree T r of T ,

|T r| ≥ l 8 if T r contains a node different from L[i].
• Every incomplete node of M belongs to a tree of T or is one of the last |L| -i nodes of L. By the first and third properties and the condition at line 4 of Algorithm 6, node u belongs to a unique tree T u ⊆ G of T . Once the agent occupies node u, the tree T u is pruned via the procedure Prune(l) at line 7 of Algorithm 6. The pseudocode of procedure Prune is detailed in Algorithm 7.

Algorithm 7: Prune(l)

1 v := the current node; 2 T v := the tree of T containing node v;

3 T := T \ {T v }; 4 Root T v at node v; 5 foreach node u of T v such that d Tv (u, v) = max{1, l 4 } do 6
T u := the subtree of T v rooted at u;

7 if Tu (u) ≥ l 4 -1 then 8 T := T ∪ {T u }; 9
Remove from T v all nodes that belong to T u and all edges that are incident to a node of T u ;

10 T := T ∪ {T v };
In the context of iteration I, the pruning operation will transform T u into a tree T u such that T u (u) ≤ l 2 -1, while preserving the three properties listed above: this offers two important advantages to which we will return at the end of this section. Once the pruning is done, the agent applies function Explore(l, bound), whose pseudocode is given in Algorithm 8. In the pseudocodes of LocalExpansion and of Explore, variable bound corresponds at any stage to the number of remaining edges the agent is authorized to traverse outside of B f (G, s). In the context of iteration I, function Explore(l, bound) permits the agent to explore tree T u and to execute function CDFS( l 2 , bound) from the nodes of T u that are incomplete in M, as long as variable bound remains non-negative. These executions of CDFS occuring during the exploration of T u create in turn trees that are added to T (cf. line 8 of Algorithm 8) and that contain the new incomplete nodes of M. If the return value of function Explore(l, bound) is non-negative, we will show in Section 5 that all the nodes of T u have become complete in M. Under the same condition, we will also guarantee that each tree T r, which has been added to T during the execution of function Explore, contains an incomplete node only if |T r| ≥ l 8 . Both these guarantees combined with lines 9 to 12 of Algorithm 6 will allow us to show that our three properties will be satisfied for the next iteration I , if any, even if it occurs in another call to LocalExpansion (in the same execution of GlobalExpansion(l, m)). In particular, this is made possible by the fact that T is never reset between the calls to LocalExpansion during the execution of the while loop of Algorithm 4.

To fully appreciate the process accomplished during I, we need to come back to the two aforementioned advantages that are brought by the pruning operation. The first advantage concerns the height of T u . The fact that T u (u) ≤ l 2 -1 is a key element to control the maximal distance between the agent and node s. Without this, the agent could go too far from node s and we would not be able to guarantee that the agent explores only edges of B f +2l-1 (G, s) during the execution of GlobalExpansion(l, m) (which is a crucial property as pointed out in Section 3). The second advantage concerns the size of T u . The pruning operation preserves the second property, and thus (1) T u corresponds to a tree containing only node

L[i] or (2) |T u | ≥ l
8 . This implies that the cost resulting from the moves of line 6 of Algorithm 6 and line 5 of Algorithm 8 is linear in the size of T u . Besides, if bound is still non-negative at the end of Explore(l, bound), all the nodes of T u have become complete (it is in particular the case for node u) and the tree is removed from T through line 9 of Algorithm 6. After this removal, no edge of T u will be an edge of another tree of T till the end of the execution of GlobalExpansion(l, m). As a result, if the return value of Explore(l, bound) is non-negative in I, we can associate the moves of line 6 of Algorithm 6 and line 5 of Algorithm 8 to at least one node that becomes complete during I and to at least l 8 edges that will no longer be edges of any tree of T till the end of the execution of GlobalExpansion(l, m).

In our analysis, this association will enable us to amortize efficiently the number of times the agent retraverses the edges that have been already explored during any previous iteration of the considered while loop. This will be a decisive argument to show the cost of O(e(f ) + m) for the execution of GlobalExpansion(l, m) in the case where l ≥ 2 and m =⊥.

Correctness and complexity analysis

This section is dedicated to the proof of correctness and of complexity of Algorithm TreasureHunt(x) in the unrestricted model. TreasureHunt(x) is an exploration algorithm that can be executed also if there is no treasure in G. We first establish several exploration properties of our algorithm or of its components assuming that there is no treasure in G. In fact, this assumption concerns all the lemmas (and only them) of this section and it will not be repeated in their statements in order to lighten the presentation. After the series of lemmas, we show the main result of this section, namely Theorem 5.1, which specifies that our algorithm allows to find the treasure at a cost quasi-linear in e(d).

Throughout the proof of correctness, we will often have to consider the value of the global variable M before or after some executions. To this end, we introduce the following convention: given an execution E of Algorithm TreasureHunt(x) or some part of it, we denote by M 1 (E) the value of M at the beginning of E and by M 2 (E) the value of M at the end of E.

We start by giving two lemmas concerning the function CDFS(l, b). They list some properties that will be useful in the sequel. They are direct consequences of Algorithm 5 and can be easily proved by induction on l. • Let G be the subgraph of G that has been explored during

E. G ⊆ B l (G, u), |M 1 (E) G| = 0, M 1 (E) G = M 2 (E), T r is a spanning tree of G and i = b -|G| ≥ -1.
• The cost of E is 2|G| and T r (u) ≤ l.

• If i ≥ 0 then for every node v of T r such that d T r (u, v) < l, v is complete in M 2 (E). If i = -1, then there exists a node v of T r such that d T r (u, v) ≤ l -1 and v is incomplete in M 2 (E).
The following lemma establishes the properties of function GlobalExpansion(l, m) that will be used to prove Lemma 5.4 that concerns procedure Search(x).

Lemma 5.3 Consider an execution E of function GlobalExpansion(l, m) from the source node s, where l is a positive integer and m is either a positive integer or ⊥. Assume that M 1 (E) = B f (G, s) for some integer f ≥ 0.

• if m =⊥, or m =⊥ and l = 1, then E terminates at node s and during E the agent always knows a path in G of length at most f + 2l -1 from node s to its current node.

• If m =⊥ and l = 1 then the cost of E is O(e(f + 1)) and B f +1 (G, s) = M 2 (E).

• If m =⊥ and function GlobalExpansion(l, m) returns true (resp. false) then

B f +l (G, s) ⊆ M 2 (E) (resp. B f (G, s) ⊆ M 2 (E
) and e(f +2l-1) > e(f )+m) and the cost of E is O(e(f )+m).

Proof. First observe that the global variable M is always a subgraph of G during E. This comes from the fact that M 1 (E) = B f (G, s), and from lines 5 to 13 of Algorithm 5 that are the only places where M may be modified during E. By line 2 of Algorithm 4, L is an array containing all the nodes of the boundary of B f (G, s). By definition, the nodes of B f (G, s) that are not in L are necessarily complete in M 1 (E).

According to Algorithm 4, the edge traversals made during E can be divided into three distinct types. The first type corresponds to those that aim to position the agent at each node of L (cf. line 6 of Algorithm 4). The second type consists of edge traversals that aim to expand M (cf. lines 9, 11 and 13 of Algorithm 4). The third type consists of edge traversals that permit to relocate the agent at node s at the end of E (cf. line 15 of Algorithm 4). The total number of edge traversals made by the agent will be analysed below and will vary according to different cases. However, with a few arguments, we can already give some properties of the first and third types, in particular concerning their order of magnitude.

Note that an execution of CDFS( Let us now turn our attention to the main case where m =⊥ and l ≥ 2. The analysis of this case will involve the global variable T . Strictly speaking, the value of this variable will be always a set of trees. However, if a node (resp. edge) belongs to a tree of T , we will sometimes say by abuse of language that it is a node (resp. an edge) of T . Still by abuse of language, we will sometimes say that a node (resp. an edge) has been removed from T , if at some point this node (or this edge) no longer belongs to any tree of T . The first while loop of Algorithm 6 will be called W 1, and when we speak of variable bound, it will be always implied it is the variable of Algorithm 6 unless explicitly mentioned otherwise. The ith execution of function LocalExpansion(l, b), if any, made within E will be denoted by LE i . The starting node of LE i is node L[i] according to line 6 of Algorithm 4 and line 13 of Algorithm 6.

(E) = M 1 (E) G ⊆ B f +1 (G, s), |B f (G, ∫ ) G| =
We start with two claims.

Claim 5.2 For every 1 ≤ i ≤ |L|, execution LE i terminates, and during it the agent always knows a path of length at most 2l -1 from node L[i] to its current node. Moreover, at the beginning and at the end of each iteration of W 1 made during LE i , we have the following three properties.

• The agent is at node L[i].

• Variable T is a set of node disjoint trees that are all subgraphs of M.

• Every incomplete node in M is a node of T or one of the last |L| -i nodes of L.

Proof of the claim. Consider an integer 1 ≤ i ≤ |L| and suppose that the agent ends up executing LE i . Let us first analyse what happens during a given iteration I of W 1 made during LE i , assuming that at the beginning of the considered iteration the three properties of the claim are satisfied. The existence of I implies that bound is non-negative at the start of I.

Once the execution of the move instruction of line 6 of Algorithm 6 has been made, the agent occupies a node u of M 1 (I). In view of line 5, node u is incomplete in M 1 (I) and the agent has reached it by following a path of length at most l from L[i]. By assumption, node u belongs to a unique tree T u of T and T u ⊆ M 1 (I). By Algorithm 7, we know that after the execution of function Prune(l) at line 7 of Algorithm 6, T is unchanged, or T u has been replaced in T by smaller node disjoint trees that are all subgraphs of T u and whose union spans T u . In particular, we have

T u (u) ≤ l 2 -1
, where T u is the tree of T containing node u after the pruning operation. After that, the agent executes function Explore(l, bound) from node u. By Algorithm 8, this execution consists of a traversal of T u interlaced with executions of CDFS from the incomplete nodes of T u (from each of these nodes, the distance in M 1 (I) to node L[i] and to node s are respectively at most l + l 2 -1 and at most f + l + l 2 -1). The first parameter of these executions of CDFS is l 2 . Hence, in view of Lemma 5.2, we know that after the execution of function Explore in line 8 of Algorithm 6, variable bound ≥ -1 and variable M has been extended by the subgraph K of G that has been explored in the calls to CDFS made during Explore(l, bound). In view of the same arguments, we know that the trees added to T during the execution of function Explore are all subgraphs of M at the end of this execution: precisely, the union of these added trees forms a spanning subgraph of K, and thus the third property of the claim is still satisfied. In addition, during the execution of Explore(l, bound), the agent always knows a path of length at most l -1 from node u to its current node, due to Lemma 5.1 and to the fact that T u (u) ≤ l 2 -1. Note that once the process of line 8 of Algorithm 6 is over, T is indeed still a set of trees that are all subgraphs of M, but some trees of T may be not node disjoint. This is resolved through the executions of lines 9 to 12 of Algorithm 6, that will permit to guarantee the second property of the claim while preserving the third property.

Finally, taking into account line 13 of Algorithm 4 that consists of an execution in the reverse order of all the edge traversals that have been previously made in I, it follows from the above explanations that I terminates and the agent always knows a path of length at most 2l -1 from L[i] to its current node during I. It also follows that the conditions that are supposed to be satisfied at the beginning of I, are still satisfied at the end of I. If variable bound is negative at the end of I, there will be no more iterations of W 1 thereafter in LE i and even in E.

Note that, outside of W 1, the position of the agent does not change within LE i . It is also the case for variable T , except just before W 1 where the node L[i] is added into T if and only if L[i] is incomplete in M and L[i] belongs to no tree of T . Also note that at the beginning of the first call to function LocalExpansion(l, b), we have b = m, T = ∅ and the agent occupies node L [START_REF] Alpern | The Theory of Search Games and Rendezvous[END_REF]. In particular, this implies that the initial assumptions made for the analysis of iteration I are satisfied just before the execution of W 1 in the first call to function LocalExpansion. Hence, it follows by induction on i, that all the statements of the claim hold, except the statement that LE i terminates if bound is never negative. More specifically, it can be shown that each iteration of W 1 in LE i terminates, but at this point of the proof, we are not yet sure that the number of these iterations is finite if bound is never negative. So, to conclude the proof of this claim, it remains to show that the number of iterations of W 1 in LE i is finite assuming that variable bound is never negative in LE i . During an iteration I of LE i , the node u to which the agent moves when executing line 6 of Algorithm 6 is necessarily incomplete in M 1 (I) and such that d M 1 (I) (L[i], u) ≤ l. Using Lemma 5.2, we can prove that node u becomes complete in M after the first call to CDFS made within the execution of Explore(l, bound) in I because the return value of this execution, which becomes by then the value of bound, is necessarily at least 0 (otherwise we get a contradiction with the assumption that variable bound is never negative in LE i ). Since the number of nodes u such that d G (l[i], u) ≤ l is finite, it follows that the number of iterations in LE i is finite even if variable bound is never negative in LE i . This concludes the proof of the claim.

In view of Claims 5.1 and 5.2, we are guaranteed that E terminates (at node s) and the number of calls to CDFS made during E is finite. As pinpointed in the proof of Claim 5.2, these calls are triggered only through the executions of function Explore from nodes that necessarily belong to B f +l+ l 2 -1 (G, s). Hence, using Lemma 5.2, the next claim can be shown by induction on the number of calls to CDFS made during E. In this claim and in the rest of this proof, H denotes the subgraph of G consisting of all the edges and nodes that have been visited by the agent during the calls to CDFS within E.

Claim 5.3 The total cost of the executions of

CDFS in E is 2|H|, M 2 (E) = M 1 (E) H ⊆ B f +2l-1 (G, s) and |M 1 (E) H| = 0. Moreover, at the end of E, the value of variable b in Algorithm 4 is m -|H| ≥ -1.
Note that in view of Claims 5.1 and 5.2, the agent always knows a path of length at most f + 2l -1 from node s to its current node during E. Suppose that m -|H| = -1. In this case, function GlobalExpansion(l, m) returns false, and Now, suppose that that m -|H| ≥ 0. In this case, variable bound is never negative and function GlobalExpansion(l, m) returns true. Moreover, we have the following claim.

B f (G, s) ⊆ M 2 (E) as M 2 (E) = B f (G,
Claim 5.4 B f +l (G, s) ⊆ M 2 (E).
Proof of the claim. Assume by contradiction that the claim does not hold. Since M 2 (E) = B f (G, s) H, it follows that there exist an integer k and a node

u of M 2 (E) such that d M 2 (E) (L[k], u) ≤ l and u is incomplete in M 2 (E). Without loss of generality, suppose that in M 2 (E), L[k]
is the node of L that is the closest (or one the closest) from node u. This implies that, at the end of each iteration of W 1 made during LE k , there is a node v that does not belong to the last |L| -k nodes of L, that is incomplete in M and that is such that d M (L[k], v) ≤ l. Hence, the execution LE k never terminates, as the condition of W 1 (cf. line 4 of Algorithm 6) always evaluates to true during LE k in view of Claim 5.2 and of the fact that variable bound is never negative. We then get a contradiction with the fact that E terminates, which concludes the proof of the claim.

Consequently, to end the analysis of the current case (and thus the proof of this lemma), it remains to prove that the cost that has been paid during E is O(e(f ) + m). More precisely, in view of Claim 5.1, it is enough to show that the number of moves of the second type (which correspond here to the moves made during the executions of function LocalExpansion) belongs to O(m). Actually, a first step has been made via Claim 5.3 that implies that the number of moves of the second type made during the executions of CDFS is at most 2(m + 1). Hence, we just have to prove that the number of moves of the second type made outside of the executions of CDFS and outside of the executions of line 13 of Algorithm 6 is O(m). These remaining moves are of two kinds. The first kind concerns those that are made during the execution of line 5 of Algorithm 8 in order to make the DFS traversal of a tree of T : they will be called the blue moves. The second kind concerns those that are made during the execution of line 6 of Algorithm 6: they will be called the red moves. To conduct the discussions, we need two more claims.

Claim 5.5 Suppose that at some time t during E, a tree is removed from T via the execution of line 9 of Algorithm 6. For every edge e of the removed tree, e will not be in T from time t to the end of E.

Proof of the claim. The edges of T always originally come from the trees returned by the calls to function CDFS. According to Lemma 5.2, for any of these calls F , the returned tree T r has no common edge with M 1 (F ) and M 1 (F ) T r ⊆ M 2 (F ). This implies that at any point of execution E, every edge e of G belongs to at most one tree of T (the operation of pruning and merging of lines 7 and 12 of Algorithm 6 can never change this fact). This also implies that for every edge e of G, there is at most one call to function CDFS in E that returns a tree containing edge e. Hence, when a tree is removed from T , none of its edges will ever appear again in T from the time of the removal to the end of E. This proves the claim.

Claim 5.6 At the beginning of each execution of function Explore(l, bound) in LE i , we have the following property P (i): for each tree T r of T ,

|T r| ≥ l 8 if T r contains a node different from L[i].
Proof of the claim. Suppose by contradiction that the claim does not hold and suppose that i is the smallest integer for which the claim is not verified. Let I be the first iteration in LE i such that P (i) is not satisfied at the beginning of the execution of function Explore(l, bound) in I. Let u (resp. T u ) be the node (resp. the tree of T ) in which the agent is located at the end of the execution of line 6 of Algorithm 6.

If no iteration of W 1 has been made before I in E, then at the beginning of I, T is either empty or contains only node L[i] in view of lines 2 to 4 of Algorithm 6. This is still true after the pruning operation in I and thus at the beginning of the execution of function Explore(l, bound) in I. This is a contradiction. Hence, at least one iteration of W 1 has been made before I in E. Denote by I the iteration preceding I. If I occurs during LE i , we know that property P (i) is satisfied at the beginning of the execution of function Explore(l, bound) in I . At the end of this execution, variable bound is necessarily non-negative or otherwise we get a contradiction with the existence of I. By Lemma 5.2 and Algorithm 8, this implies that for each tree T r added into T during this execution of function Explore, |T r| < l 2 only if all the nodes of T r are complete in M at the end of the execution of function Explore. Hence, in view of lines 9 to 12 of Algorithm 6, property P (i) is still true at the beginning of I. This implies that property P (i) is also true at the beginning of the execution of function Explore(l, bound) in I in view of Algorithm 7. Indeed, via the pruning operation Prune(l) occuring in I, T u remains unchanged if Tu (u) < l 4 , and it cannot be split into trees of size less than l 8 otherwise. This is again a contradiction. Consequently, I is the last iteration of W 1 in LE k for some 1 ≤ k < i and I is the first iteration of W 1 in LE i . By assumption, property P (k) is satisfied at the beginning of the execution of function Explore(l, bound) in I and, using the same arguments as above, we know that property P (k) is still true at the end of I . Note that at the end of I , node L[k] is necessarily complete. Indeed, otherwise we get a contradiction with the fact that I is the last iteration of W 1 in LE k in view of Claim 5.2 and line 4 of Algorithm 6. We can state that node L[k] belongs to a tree containing a node different from L[k] at the the end of I , because otherwise it could not be in T at this time in view of line 9 of Algorithm 6. As a result, the size of every tree of T is at least l 8 at the end of I . Moreover, from the end of I to the beginning of I, T is subject to no change except the possible insertion of the one-node tree L[i], in view of lines 2 to 4 of Algorithm 6. Consequently, property P (i) is satisfied at the beginning of I. As explained above, this implies that property P (i) is also true at the beginning of the execution of function Explore(l, bound) in I, which is again a contradiction and proves the claim. Now, consider an iteration I of W 1 in LE i during which at least one blue or red move is made. At the beginning of function Explore(l, bound) in I, we know that the agent occupies an incomplete node u belonging to a tree T r of T . Moreover, the size of T r is at least l 8 . Indeed, if it is not the case, T r is then the one-node tree L[i] in view of Claim 5.6: thus the agent does not make at least one blue or red move during I, which is a contradiction with the definition of I. The number of blue moves (resp. red moves) in I is at most 2|T r| (resp. at most l), which gives a total cost of at most 10(|T r| + 1) for these two kinds of moves in I. The edges of T r originally come from trees returned during some previous calls to CDFS and thus they all belong to H in view of Lemma 5.2 and the definition of H. First suppose that the execution of Explore(l, bound) returns a non-negative integer. In view of Lemma 5.2 and Algorithm 8, we know that all the nodes of T r (including node u) are complete in M at the end of it. If |T r| > 0, the number of blue or red moves in I is at most 20|T r| and they can be associated to |T r| edges of H that will be removed from T via the execution of line 9 of Algorithm 6 in I: after that, these removed edges will never appear anymore in T during E by Claim 5.5. If |T r| = 0, the number of blue or red moves in I is at most 10. These moves can be associated to node u of T r that becomes complete in M during a call to CDFS made in the execution of Explore, and that remains so till the end of E. Since u is visited during a call to CDFS, it necessarily belongs to H. Now, suppose that the execution of Explore(l, bound) returns a negative integer in I. This means that I is the last execution of W 1 in E and the number of blue or red moves during this last execution of W 1 is at most 10(|H| + 1) as |T r| ≤ |H|. From the above arguments, it follows that the number of blue or red moves in E is at most 30|H| + 10z + 10 where z is the number of nodes in H. Since H is not necessarily a connected graph, it is not straightforward that z can be upper bounded by a linear function in |H|. Hence, we need this last claim. Claim 5.7 z is at most 2|H| + 1.

Proof of the claim. Suppose by contradiction that z ≥ 2|H| + 2. This means that there exist two nodes u and u of H that have no incident edge in H. Recall that H is the graph consisting of the nodes and edges that have been explored during the executions of CDFS that are triggered throughout the calls to function Explore(l, bound). Hence, node u (resp. u ) can belong to H only if one of these executions of CDFS has been launched from node u (resp. u ). Denote by X (resp. X ) this execution of CDFS and suppose without loss of generality that X occurs before X . By Algorithm 8, at the beginning of X node u is incomplete in M. If at the end of X, node u is still incomplete in M, then, by Lemma 5.2, the value of variable bound of Algorithm 6 is -1 at the end of X. Hence X cannot exist, which is a contradiction. As a result, node u becomes complete in M during X. This means that at least one edge e incident to u is visited during X and thus e belongs to H. This contradicts the definition of node u and proves the claim.

In view of the above claim, the number of blue or red moves in E is at most 50|H| + 20, which is O(m) by Claim 5.3. This closes the analysis of the case where l ≥ 2 and m =⊥, and thus completes the proof of the lemma.

Below is the lemma establishing the properties of procedure Search(x) that will be used to show the main theorem of this section. The proof of this lemma relies on Lemma 5.3. Lemma 5.4 Consider an execution E of procedure Search(x) from the source node s, for any real constant x > 0. Assume that M 1 (E) = B f (G, s) for some integer f ≥ 0.

• The execution terminates at node s and during the execution the agent always knows a path in G of length at most max{f + 1, (1 + x)f } from node s to its current node.

• There exists an integer f > f such that M 2 (E) = B f (G, s) and at least one of the following properties holds:

1. The cost of E is O(e(f + 1)) and xf < 3.

The cost of

E is O(e(f )) and f > (1 + x 3 )f . 3. The cost of E is O(e(f ) log(f + 2)) and e(f + 1) ≥ 2e(f ). 4. The cost of E is O(e(f + 1)) and e(f + 1) ≥ 2e(f ).
Proof. The execution of procedure Search(x) from node s can be viewed as a sequence S of consecutive executions E 0 , E 1 , E 2 , . . . in which E i corresponds to the ith execution of the while loop of Algorithm 3 if i ≥ 1, and to the instructions before the while loop of Algorithm 3 otherwise. The length of S, i.e., the number of executions E i in S, will be denoted by |S| (we show below that |S| is finite). We will often discuss the values of three specific variables of Algorithm 3 that are l, f loor and ceil: in the sequel, the values of l, f loor and ceil at the end of E k will be respectively denoted by l k , f loor k and ceil k . Observe that the existence of E i+1 implies that l i ≥ 1 according to the while loop of Algorithm 3. Also observe that the value of variable f loor is always a non-negative integer that never decreases, and the second parameter of each call to function GlobalExpansion is always a positive integer (cf. condition of the while loop of Algorithm 3) except for the first call in which it is ⊥. These observations, which condition the validity of several subsequent arguments, must be kept in mind when reading the proof as they will not always be repeated in order to lighten the text.

We start by showing two claims.

Claim 5.8 For every 0 ≤ k ≤ |S| -1, E k starts and ends at node s, M 2 (E k ) = B f loor k (G, s) and f loor k + 2l k -1 ≤ ceil k ≤ (1 + x)f .
Proof of the claim. We prove the claim by induction on k and we begin with the base case k = 0. Execution E 0 essentially consists of a call to GlobalExpansion(1, ⊥) from node s. By assumption we have M 1 (E 0 ) = B f (G, s). Hence, according to Lemma 5.3, E 0 terminates at node s and M 2 (E 0 ) = B f loor 0 (G, s). Moreover, in view of lines 2 and 4 of Algorithm 3, we have f loor 0 = f + 1 and f loor 0 + 2l 0 -1 ≤ ceil 0 ≤ (1 + x)f , which concludes the base case k = 0. Now, assume that there is an integer 0

≤ k ≤ |S| -2 such that E k terminates at node s, M 2 (E k ) = B f loor k (G, s) and f loor k + 2l k -1 ≤ ceil k ≤ (1 + x)f
. We prove below that these properties also hold for k + 1.

Execution E k+1 essentially consists of a call to GlobalExpansion(l k , m). By the inductive hypothesis, E k+1 starts at node s and M 1 (E k+1 ) = B f loor k (G, s). It then follows from Lemma 5.3 that E k+1 terminates at node s, and

B f loor k +l k (G, s) ⊆ M 2 (E k+1 ) if GlobalExpansion(l k , m) returns true, B f loor k (G, s) ⊆ M 2 (E k+1 ) otherwise.
Note that according to lines 7 to 10 of Algorithm 3, f loor k+1 = f loor k + l k if GlobalExpansion(l k , m) returns true, f loor k+1 = f loor k otherwise. Thus, in view of line 11 of Algorithm 3, we have M 2 (E k+1 ) = B f loor k+1 (G, s). Finally, it remains to prove that f loor k+1 + 2l k+1 -1 ≤ ceil k+1 ≤ (1 + x)f . If GlobalExpansion(l k , m) returns true, then ceil k+1 = ceil k and l k+1 = ceil k+1 -f loor k+1 2 (cf. line 8 of Algorithm 3), which implies, in view of the inductive hypothesis, that f loor k+1 + 2l k+1 -1 ≤ ceil k+1 ≤ (1 + x)f . If GlobalExpansion(l k , m) returns false, then ceil k+1 = f loor k + 2l k -1, f loor k+1 = f loor k (cf. line 10 of Algorithm 3) and l k+1 = l k 2 which also implies, in view of the inductive hypothesis, that f loor k+1 + 2l k+1 -1 ≤ ceil k+1 ≤ (1 + x)f . This concludes the inductive proof of the claim.

Claim 5.9 |S| is in O(log(f + 2)).
Proof of the claim. If |S| = 1, the claim trivially holds. Hence, suppose that |S| ≥ 2 and fix any integer 1 ≤ i ≤ |S| -1. We show below that there is an integer c ≤ 3 such that l i+c ≤ 7l i 8 or i ≥ |S| -6. This is enough to prove the claim. Indeed, the above property implies that |S| is O(log(f + 2)) because l 1 is at most linear in f by Claim 5.8 and because we exit the while loop when the value of variable l becomes less than 1. We consider two cases.

• Case 1: the execution of GlobalExpansion(l i-1 , m) returns true in E i and i ≤ |S| -3. (Note that executions E i+1 and E i+2 exist as i ≤ |S| -3). By line 8 of Algorithm 3, we get l i = ceil i -f loor i

2

. Let i ≤ j ≤ i + 2 be the largest integer such that the return value of GlobalExpansion is true from the execution E i to E j included. In view of line 8 of Algorithm 3 and the fact that l i = ceil i -f loor i 2 , if j = i + 2 then l i+2 cannot be more than l i 2 . Still from the same arguments, we know that variable l never increases from the end of E i to the end of E j , and thus l j ≤ l i . Hence, if j < i + 2, the return value of GlobalExpansion is false in E j+1 , which implies, according to line 10 of Algorithm 3, that l j+1 ≤ l j 2 ≤ l i 2 . Consequently, in the first case, l i+1 or l i+2 is at most l i 2 .

• Case 2: the execution of GlobalExpansion(l i-1 , m) returns false in E i and i ≤ |S| -4. (Note that executions E i+1 to E i+3 exist as i ≤ |S| -4). By line 10 of Algorithm 3, we get l i = l i-1 2 and ceil i -f loor i = 2l i-1 -1. If the execution of GlobalExpansion returns also false in E i+1 , then we have l i+1 ≤ l i 2 . So, suppose that the execution of GlobalExpansion returns true in E i+1 . We then have

l i+1 = ceil i+1 -f loor i+1 2 = ceil i -f loor i -l i 2 = 2l i-1 -1-l i 2
. Furthermore, i + 1 ≤ |S| -3. Thus, using the same reasoning as in Case 1 (but replacing i by i + 1), we have l i+2 ≤ l i+1 2 or l i+3 ≤ l i+1 2 . We consider three subcases.

-Subcase 2.1: l i-1 is even. We have

l i+1 = 2l i-1 -1-l i 2 = 3l i -1 2 ≤ 3l i 2 . Thus, l i+2 or l i+3 is at most 3l i 4 . -Subcase 2.2: l i-1 is odd and l i ≥ 2. We have l i+1 = 2l i-1 -1-l i 2 = 3l i +1 2 ≤ 7l i 4 .
Thus, l i+2 or l i+3 is at most 7l i 8 . -Subcase 2.3: l i-1 is odd, l i = 1 and i ≤ |S|-7. We have

l i+1 = 2l i-1 -1-l i 2 = 3l i +1 2 = 2.
Note that i + 2 ≤ |S| -5 and l i+1 is even. Hence, using the same reasoning as from Case 1 to Subcase 2.1 (but replacing i by i + 2), we know that l i+3 , l i+4 or l i+5 is at most 3l i+2 4 . Also note that l i-1 = 3 as l i = l i-1 2 . Thus, ceil i = f loor i + 5 since ceil i -f loor i = 2l i-1 -1. This implies that ceil i+1 = f loor i+1 + 4 in view of line 8 of Algorithm 3. Consequently, if the execution of GlobalExpansion returns true in E i+2 , we have ceil i+2 -f loor i+2 = ceil i+1 -f loor i+1 -l i+1 = 2, and thus l i+2 = 1. Besides, if the execution of GlobalExpansion returns false in E i+2 , we immediately have l i+2 = l i+1 2 = 1. As a result, l i+3 , l i+4 or l i+5 is less than 1, which means that i ≥ |S|-6 and contradicts the assumption that i ≤ |S| -7.

To summarize, we have shown that i ≥ |S| -6 or there is an integer c ≤ 3 such that l i+c ≤ 7l i 8 . This concludes the proof of the claim.

According to Claims 5.8 and 5.9, S terminates after O(log(f + 2)) iterations of the while loop, and

M 2 (E) = M 2 (E |S|-1 ) = B f loor |S|-1 (G, s) with f loor |S|-1 ≥ f loor 0 > f .
By assumption, E 0 starts at node s and M 1 (E 0 ) = B f (G, s). It then follows from Lemma 5.3 that the agent always knows during E 0 a path in G of length at most f + 1 from s to its current node. By Claim 5.8, for every 1 ≤ k ≤ |S| -1, E k starts at node s and M 1 (E k ) = B f loor k (G, s). Hence, from Lemma 5.3 and Claim 5.8, it follows that for every 1 ≤ k ≤ |S| -1, the agent always knows during E k a path in G of length at most f loor k-1 + 2l k-1 -1 ≤ ceil k-1 ≤ (1 + x)f from s to its current node. This completes the proof of the first part of the lemma. Now, we prove the second part. To do so, it is enough to show that one of the four properties of the second part is satisfied with f = f loor |S|-1 as M 2 (E) = B f loor |S|-1 (G, s) and f loor |S|-1 > f . Since E 0 starts at node s and M 1 (E 0 ) = B f (G, s), it follows from Lemma 5.3 that the cost of E 0 is O(e(f + 1)). After E 0 , the condition of the while loop in Algorithm 3 evaluates to false (and thus |S| = 1) if and only if l 0 < 1 or |M 2 (E 0 )| ≥ 2e(f ) i.e., if and only if xf < 3 or e(f loor 0 ) ≥ 2e(f ). As a result, if |S| = 1, f = f loor |S|-1 = f loor 0 = f + 1 and the first or the fourth property are satisfied.

So, assume that |S| ≥ 2. From the above explanations we have xf ≥ 3.

In E 1 , the agent executes GlobalExpansion(l 0 , m) where m is e(f ) in view of line 1 of Algorithm 3. We stated earlier that E 0 is in O(e(f + 1)). Besides, M 2 (E 0 ) = B f +1 (G, s) by Claim 5.8. Consequently, the existence of E 1 and the condition of the while loop of Algorithm 3 imply that |M 2 (E 0 )| = e(f + 1) < 2m = 2e(f ), and we get the following claim. Proof of the claim. We prove the claim by induction on k and we start with the base case k = 1. By Claim 5.8, M 1 (E 1 ) = B f loor 0 (G, s) and E 1 starts at node s. From this, Lemma 5.3 and the fact that GlobalExpansion(l 0 , m) returns false, we have e(f loor 0 + 2l 0 -1) > e(f loor 0 ) + m. Since m = e(f ), ceil 1 = f loor 0 + 2l 0 -1 (cf. line 10 of Algorithm 3) and e(f loor 0 ) ≥ e(f ) as f loor 0 = f + 1, we get e(ceil 1 ) > 2e(f ), which concludes the base case k = 1. Now, assume that there is an integer 1 ≤ k ≤ |S| -2 such that e(ceil k ) > 2e(f ). We prove that e(ceil k+1 ) > 2e(f ). By Claim 5.8, E k+1 terminates. If GlobalExpansion(l k , m) returns true then ceil k+1 = ceil k , which implies that e(ceil k+1 ) > 2e(f ) as e(ceil k ) > 2e(f ) by the inductive hypothesis. Otherwise, GlobalExpansion(l k , m) returns false: in view of Lemma 5.3 and Claim 5.8, we then have e(f loor k + Variable M can be modified only through the instructions of line 2 of Algorithm 2, line 11 of Algorithm 3 and lines 5 to 13 of Algorithm 5. In view of these instructions, the value of M is always a subgraph of G whose nodes and edges have been explored by the agent. Thus, we know that for every integer 1 ≤ i ≤ |S|, B d (G, s) M 1 (S i ). Indeed, if it was not the case for some i, we would get a contradiction with the existence of S i , as this would mean that the treasure has been found before the start of S i . Note that |S| ≤ d because if S d+1 existed, we would have B d (G, s) ⊆ M 1 (S d+1 ) in view of Lemma 5.5.

For every 1 ≤ i ≤ |S|, we denote by f i the integer such that M 1 (S i ) = B f i (G, s). The existence and the unicity of each of these integers are guaranteed by Lemma 5.5 and the fact that B d (G, s) M 1 (S i ). Still by Lemma 5.5, we know that for every 1

≤ i < |S|, 0 ≤ f i < f i+1 .
From all the above explanations, we get the following claim.

Claim 5.12 |S| ≤ d, the treasure is found by the end of S, and for every

1 ≤ i < |S|, 0 ≤ f i < f i+1 < d.
Since the agent ends up finding the treasure, it remains to discuss the incurred cost.

Note that in view of Lemma 5.5, there is an integer

f |S|+1 such that M 2 (S |S| ) = B f |S|+1 (G, s).
However, we may have several candidates for f |S|+1 because M 2 (S |S| ) may be G. In the rest of this proof, f |S|+1 is choosen as the smallest integer that satisfies one of the four properties of the second part of Lemma 5.4 (with f = f |S|+1 , and

f = f |S| since M 1 (S |S| ) = B f |S| (G, s)).
In view of Lemma 5.4, we know that for each execution S i in S, at least one of the four properties of the second part of Lemma 5.4 is satisfied with f = f i and f = f i+1 : the execution is then said to be of type 1 ≤ j ≤ 4 if it satisfies the jth property. The cost of S is upper bounded by C 1 + C 2 + C 3 + C 4 where C j is the total cost of the executions of type j in S. So, to prove the theorem, it is enough to prove that C 1 , C 2 , C 3 and C 4 all belong to O(e(d) log d). This is the purpose of the rest of this proof.

First, consider the case of C 1 . We know from Lemma 5.5 that if i ≥ 3

x + 1, then f i ≥ 3

x , which means that f i x ≥ 3 and S i cannot be of type 1 according to Lemma 5.4. Thus, the number of executions of type 1 in S is at most 3

x . Moreover, if S i is of type 1, its cost is O(e(f i + 1)) and f i < d in view of Lemma 5.4 and Claim 5.12. Hence, C 1 is in O(e(d)), which is O(e(d) log d). Now, consider the case of C 2 . If S i is of type 2, it follows from Lemma 5.4 that the cost of S i is O(e(f i )) and f i+1 > (1 + x 3 )f i . From Claim 5.12, we must have f i < d. Moreover, f 1 = 0 and by Lemma 5.5 f i > f i-1 for every 2 ≤ i ≤ |S|. Hence, the number of executions of type 2 in S is O(log d) and the cost of each of them is O(e(d)). This implies that C 2 is in O(e(d) log d).

Let us turn attention to the case of C 3 . From Lemma 5.4, there is a constant c > 0 such that for every 1 ≤ i ≤ |S|, we have the following: if S i is of type 3, then e(f i+1 + 1) ≥ 2e(f i ) and the cost of

S i is at most c • e(f i ) log(2 + f i ) = h(f i ). Let h(f i ) = c • e(f i ) log(2 + f i )
. Let i * be the smallest integer, if any, such that S i * is of type 3 and i * = i + 2k for some integer k ≥ 1. From the above explanations and from Claim 5.12, it follows that, if S i is of type 3, then f i * ≥ f i+2 ≥ f i+1 + 1 > f i and e(f i * ) ≥ e(f i+1 + 1) ≥ 2e(f i ), which means that h(f i * ) ≥ 2h(f i ). Let k (resp. k ) be the largest even (resp. odd) integer, if any, such that S k (resp. S k ) is of type 3. By the telescopic effect, the sum of the costs of the executions S i of type 3 such that i is even (resp. odd) is at most 2h(f k ) (resp. 2h(f k )). Since by Claim 5.12, f i < d for every 1 ≤ i ≤ |S|, we know that 2h(f k ) as well as 2h(f k ) is at most 2c • e(d) log(1 + d). Hence, C 3 is in O(e(d) log d).

Using, as above, arguments based on the telescopic effect, we can show that C 4 is in O(e(f k + 1))

where k is the largest integer, if any, such that S k is of type 4. Since f k < d, C 4 is in O(e(d)), which is O(e(d) log d). This concludes the proof of the theorem.

6 Treasure hunt with restrictions Theorem 5.1 holds for the task of treasure hunt without any restrictions on the moves of the agent, for all locally finite graphs, both finite and infinite. In this section we show how to modify our treasure hunt algorithm to make it work under the fuel-restricted and the rope-restricted models for finite graphs.

Strictly speaking, the fuel-restricted model was defined in [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF] assuming that both the constant α > 0 and the radius r were known to the agent. On the other hand, the rope-restricted model was defined in [START_REF] Duncan | Optimal constrained graph exploration[END_REF] for any known constant α > 0 and for unknown radius r. We will show that, for each of these restrictive models and for any known constant α > 0, we can design a treasure hunt algorithm with the promised efficiency even when r is unknown. To this end, we need to modify the restriction of the fuel-restricted model from [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF], avoiding to reveal r to the agent by showing it the size of the tank. We fix a positive constant α, known to the agent, and we proceed as follows. For the restricted tank case from [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF], we assume that at any visit of s the agent can put as much fuel in the tank as it wants, but we show that if the (unknown) radius of the graph is r then the tank is never filled to more than B = 2(1 + α)r. The formalization of the rope-restricted model corresponds to its definition in [START_REF] Duncan | Optimal constrained graph exploration[END_REF]. Recall that the agent is attached at s by an infinitely extendible rope that it unwinds by a length 1 with every forward edge traversal and rewinds by a length of 1 with every backward edge traversal. Whenever the agent completely backtracks to s, the unwinded segment of the rope is of length 0. We show that if the (unknown) radius of the graph is r then the initial segment of the rope unwinded by the agent executing our algorithm will never be longer than L = (1 + α)r.

The following theorem states that procedure TreasureHunt can be transformed into a procedure allowing the agent to find the treasure in the aforementioned restrictive models, without changing the asymptotic complexity. Theorem 6.1 Consider a graph G of unknown radius r in which a treasure is located at an unknown distance at most 1 < d ≤ r from the starting node s of the agent. For any positive constant α, procedure TreasureHunt( α 2 ) can be transformed into a procedure allowing the agent to find the treasure at cost O(e(d) log d) in the rope-restricted model (resp. fuel-restricted model) without ever using a segment of the rope longer than (1+α)r (resp. without filling the tank to more than 2(1+α)r at any visit of s).

Proof. The execution of procedure TreasureHunt( α 2 ) from node s corresponds to a sequence S = (S 1 , S 2 , . . . , S |S| ) of executions of Search( α 2 ), in which the |S|th execution of Search( α 2 ) is interrupted prematurely because of the discovery of the treasure.

We denote by G 0 the graph consisting only of node s, and for every 1 ≤ i ≤ |S|, we denote by G i the subgraph of G that has been explored from the beginning of S 1 to the end of S i . For every 1 ≤ i ≤ |S|, the cost of S i will be denoted by c i .

According to Lemma 5.5, for every 1 ≤ i ≤ |S|, S i starts and ends at node s (except S |S| that ends at the node containing the treasure), there is an integer

f i ≥ 0 such that M 1 (S i ) = B f i (G, s) and if i < |S|, M 2 (S i ) = M 1 (S i+1
). Moreover, the value of M is always a subgraph of G whose nodes and edges have been all explored by the agent, and thus, for every 1

≤ i ≤ |S|, B f i (G, s) is a subgraph of G i-1
, f i is unique and f i < d (or otherwise the treasure would have been found before the start of S i which leads to a contradiction with the existence of this execution). Hence, from the fact that d ≤ r, we get the following claim.

Claim 6.1 For every 1 ≤ i ≤ |S|, max{f i + 1, (1 + α)f i } ≤ (1 + α)r
First, we describe a new algorithm A that permits to find the treasure, in the model without constraints, with asymptotically the same cost as that of TreasureHunt( α2 ). This new algorithm consists in executing TreasureHunt( α 2 ) with some changes in order to guarantee an extra property that will be important for our purpose. More precisely, an execution of A from node s is a sequence of executions (S 1 , S 2 , . . . , S |S| ) in which each S i has cost O(c i ) and corresponds to an emulation of execution S i . In particular, for every 1 ≤ i ≤ |S|, S i starts and ends at node s (except S |S| that ends at the node containing the treasure), M 1 (S i ) = M 1 (S i ) = B f i (G, s), and at the end of S i , G i has been entirely explored. Obviously, all of this would not be interesting without the additional crucial property brought by S i that will be called the frequent return property and that is the following. Let Sk be the stack initially empty in which we push (resp. pop) the last traversed edge if it corresponds to a forward (resp. backward) edge traversal. During S i , the size of Sk is 0 at least once during any block of 2 max{f i + 1, (1 + α)f i } consecutive edge traversals, and is never greater than max{f i + 1, (1 + α)f i }. Moreover, at the beginning of S i , the size of Sk is 0, and if i < |S|, it is also 0 at the end of S i .

Note that Algorithm A is a solution with the desired cost in the rope-restricted model, that will never use a segment of the rope longer than (1 + α)r, as for all 1 ≤ i ≤ |S|, we have max{f i + 1, (1 + α)f i } ≤ (1 + α)r according to Claim 6.1. By requiring the agent, each time the size of Sk is 0 in S i , to refuel its tank up to the limit of 2 • max{f i + 1, (1 + α)f i } (when the size of Sk is 0, the agent is at node s), we also get our objective with algorithm A in the fuel-restricted model, as the agent never runs out of fuel and 2

• max{f i + 1, (1 + α)f i } ≤ 2(1 + α)r.
Let us describe how we can construct our emulations while ensuring the features mentioned above. Consider the emulation S i of S i . Assume that at the beginning of S i , G i-1 has been entirely explored, the size of Sk is 0 and M 1 (S i ) = M 1 (S i ) = B f i (G, s). These assumptions are trivially satisfied if i = 1. We will show below that, at the end of S i , G i is entirely explored and if i < |S| the size of Sk is 0. We will also show that if i < |S| then M 1 (S i+1 ) = B f i+1 (G, s). We consider two cases.

The first case is when αf i ≥ 2. We assume for simplicity that the number of edge traversals in S i is a positive multiple of αf i 2 . As we will explain in detail, in this case the agent executes S i but interrupts it after each block of αf i 2 edge traversals, except the last one, to make a "return trip" to node s before resuming S i from where it was interrupted. The goal of these return trips is to satisfy the frequent return property. Once the agent has executed all instructions of S i , it is either at the node containing the treasure or at node s. In the first case, we know that i = |S| and S i is simply over. In the second case i < |S|, but we do not have the guarantee that the size of Sk is 0. Hence, if the agent occupies node s once it has executed all instructions of S i , it then finishes S i with what we call a close period in which it executes in the reverse order some of the last edge traversals so that the size of Sk becomes 0 at the end of S i .

Denote by v k the node in which the kth interruption occurs, and by P k the path of length at most (1 + α 2 )f i from node s to v k that is known by the agent when the interruption occurs. Note that P k necessarily exists in view of Lemma 5.4, of the initial assumptions concerning S i and of the fact that no edge traversal of S i has been skipped before the kth interruption. Also note that if there are several paths that can play the role of P k , we simply choose the lexicographically smallest shortest path among them.

Each interruption is composed of two parts. In the first interruption, the first part consists in backtracking to node s by executing in the reverse order the last αf i 2 edge traversals. The second part consists in going back to node v 1 using path P 1 to resume S i . For the kth interruption with k > 1, the first part consists in backtracking to node s by executing in the reverse order the last |P k-1 | + αf i 2 edge traversals, and the second part consists in going back to node v k using path P k to resume S i . Finally, the close period simply consists in backtracking to node s by executing in the reverse order the last αf i It follows by induction on the number of interruptions that the size of Sk is 0 at the end of the first part of each interruption. Using this, the fact that Sk is empty at the beginning of S i and the fact that for every 1

< k ≤ c i αf i 2 , |P k-1 | + αf i 2
≤ (1 + α)f i , it follows that the frequent return property is satisfied during S i .

Moreover, it follows from the above explanation that at the end of S i , G i is entirely explored and the agent is at the node containing the treasure, if i = |S|. If i < |S|, it also follows that the size of Sk is 0 at the beginning of the next emulation S i+1 , and M 1 (S i+1 ) = M 1 (S i+1 ) = B f i+1 (G, s) because M 2 (S i ) = M 2 (S i ) = M 1 (S i+1 ). Finally, concerning the cost of S i observe that the number of interruptions is c i αf i 2 -1 and during each interruption as well as during the close period the agent makes at most 2 (1 + α)f i edge traversals. The cost of S i is then upper bounded by c i + c i αf i 2

2 (1 + α)f i ≤ (1 + 2(1+α)f i αf i 2

)c i . If 2 ≤ αf i < 4, then 2 α ≤ f i < 4 α , which implies that the cost is at most (1 + 8(1+α) α )c i . Otherwise, αf i ≥ 4 and the cost is then upper bounded by (1 + 2(1+α)f i αf i

2 -1 )c i ≤ (1 + 2(1+α) α 2 -1 f i
)c i which is also at most (1 + 8(1+α) α )c i , as 1 f i ≤ α 4 . Hence, the cost of S i is O(c i ) as α is a constant, which concludes the first case.

The second case is when αf i < 2. Here, we could not apply the same strategy as that of the first case because we have αf i 2 = 0. Consequently, we adopt a slightly different strategy in which the agent executes S i but interrupts it before each of its edge traversals. As explained in detail below, the kth interruption either consists of a return trip to node s before resuming S i and making the kth edge traversal of S i , or it consists in going to the node the agent should occupy at the end of the kth edge traversal of S i but without taking the corresponding edge: the agent then resumes S i as if it had just performed the kth edge traversal of S i (essentially it just makes some computations before interrupting again S i for the next edge traversal, if any). We will show that the latter situation will occur only when the "skipped edge" has already been traversed before by the agent. Once S i has been entirely processed, S i is simply over if the agent is located at the node containing the treasure. Otherwise, the agent is at node s and i < |S|. In this case, it executes (similarly as in the previous case) a close period in order to guarantee that the size of Sk is 0 at the end of S i .

Let us first focus on the interruptions. We denote by (u 1 , u 2 , u 3 , . . . , u c i +1 ) the sequence (with repetitions), in the chronological order, of the nodes that are visited during S i , and by (e 1 , e 2 , e 3 , . . . , e c i ) the sequence (with repetitions), in the chronological order, of the edges that are traversed during S i . Consider the kth interruption occuring at node u k just before the kth edge traversal of S i and assume that at the beginning of this interruption, the property H(k), consisting of the following three conditions, is satisfied:

• The agent has made D k ≤ f i + 1 edge traversals since the last time when Sk was empty (this could be the current time).

• The sequence of edges (e 1 , e 2 , . . . , e k-1 ) has been previously explored by the agent.

• The size of Sk has been 0 at least once during any previous block of 2(f i + 1) consecutive edge traversals and has never been greater than f i + 1.

Note that at the beginning of the first interruption, property H(1) immediately holds. We will show below that property H(k + 1) is satisfied at the beginning of the (k + 1)th interruption, if any.

In the kth interruption, the agent first checks whether it knows a path of length at most f i from node s to node u k . If this is the case, the agent executes in the reverse order the last D k edge traversals, at the end of which it is at node s and Sk is empty. Then, the agent comes back to u k using the known path of length at most f i from node s to node u k (as when αf i ≥ 2, if there are several such paths, the agent chooses the lexicographically smallest shortest among them). Once this is done, the interruption is over: the agent resumes S i and makes the kth edge traversal to reach node u k+1 . We can easily show that at the end of this edge traversal, and thus at the beginning of the next interruption if any, property H(k + 1) is satisfied.

during S i .

It follows from the above explanation that at the end of S i , G i is entirely explored and the agent is at the node containing the treasure if i = |S|. If i < |S|, it also follows that the size of Sk is 0 at the beginning of the next emulation S i+1 , and M 1 (S i+1 ) = M 1 (S i+1 ) = B f i+1 (G, s) because M 2 (S i ) = M 2 (S i ) = M 1 (S i+1 ). Finally, concerning the cost of S i , observe that the number of interruptions is c i and during the close period as well as during each interruption the agent makes at most 2(f i + 1) edge traversals. The cost of S i is then upper bounded by 2(f i + 1)c i + 2f i + 2 which is at most 2( 2 α + 1)c i + 4 α + 2, as f i < 2 α in the currently analysed case. Hence, the cost of S i is O(c i ). This concludes the second case and thus concludes the proof of the theorem.

Conclusion

We presented treasure hunt algorithms working at cost O(e(d) log d) for the unrestricted, fuelrestricted and rope-restricted models. Hence our algorithms are nearly linear in e(d) (thus refuting the conjecture from [START_REF] Awerbuch | Piecemeal graph exploration by a mobile robot[END_REF]) and at the same time almost optimal, as cost Θ(e(d)) cannot be beaten in general. The natural open problem is whether it is possible to get rid of the factor O(log d) that separates us from optimal complexity of treasure hunt.

Proposition 2 . 1

 21 For every treasure hunt algorithm A, for every integer d > 1, for every integer m ≥ d and for every integer m ≤ x ≤ m 2 , there exists a graph G of radius d such that B d (G, s) has Θ(m) nodes and Θ(x) edges and the cost incurred by A to find the treasure located at some node at distance at most d from the source node s in graph G is at least e(d, G) -1. Proof. It is enough to prove the proposition for the unrestricted model. Our proof works even if the radius d is known to the agent. Fix a treasure hunt algorithm A, an integer d > 1, an integer m ≥ d and an integer m ≤ x ≤ m 2 . We start with the construction of the following graph H. The set of nodes of H is the union of disjoint sets {s} ∪ A ∪ B, where A = {a 1 , a 2 , . . . , a d } and B = {b 1 , b 2 , . . . , b m }. The set of edges of H is the union of disjoint sets X ∪ Y ∪ Z, where X = {{s, a 1 }, {a 1 , a 2 }, {a 2 , a 3 }, . . . , {a d-1 , a d }}, Y = {{s, b 1 }, {s, b 2 }, . . . , {s, b m }}, and Z is any set of edges of size min(x, m(m -1)/2) between nodes of the set B. The graph H is connected, has 1+d+m ∈ Θ(m) nodes and d+m+min(x, m(m-1)/2) ∈ Θ(x) edges. Moreover, B d (H, s) = H and H has radius d.

Algorithm 3 : 2 ; 5 7 if success = true then 8 f 2 ; 9 else 10 ceil

 325782910 Search(x)1 v := the current node; m := |M|; 2 f loor := M (v); ceil := (1 + x) • f loor ; 3 success := GlobalExpansion(1, ⊥); 4 f loor := f loor + 1; i := 0; l := ceil-f loor while l ≥ 1 and |M| < 2m and (i = 1 or success = false) do 6 success := GlobalExpansion(l, m); loor := f loor + l; l := ceil-f loor := f loor + 2l -1; l := l 2 ;

Algorithm 4 : 9 ( 13 b

 4913 GlobalExpansion(l, m)1 v := the current node; 2 L := the array containing all the nodes of the boundary of M sorted in the order of the first visit through the DFS traversal of M from node v; 3 T := the tree produced by the DFS traversal of M from node v; 4 i := 1; b := m; T := ∅; /* T is a global variable */ 5 while i ≤ |L| and (b ≥ 0 or b =⊥) do 6 MoveTo(T, L[i]); 7 if l = 1 then 8 if b =⊥ then /* We run CDFS(1, deg(L[i])) without using its return value. */ * , * ) :=CDFS(1, deg(L[i])); 10 else /* We run CDFS(1, b) without using the second term of its return value. */ 11 (b, * ) :=CDFS(1, b); 12 else := LocalExpansion(l, b); 14 i := i + 1; 15 MoveTo(T, v); 16 return the logical value of "b ≥ 0 or b =⊥"; As one can see in lines 9 and 11 of Algorithm 4, the implementation of the case l = 1 in Algorithm 4 directly relies on function CDFS. We will see below that this function is also involved in the trickier case where l ≥ 2 and m =⊥ through the calls to function LocalExpansion. Function CDFS(l, b) permits the agent to perform a depth-first search in the zone that does not belong to M when it starts executing it. During the execution of this function M grows, augmented with the edges that are traversed by the agent. The two input parameters l ≥ 1 and b ≥ 0 are integers that bring constraints to the execution of the depth-first search. The first indicates the limit depth of the search, while the second indicates an upper bound on the number of distinct edges the agent can traverse during the search: when this bound is violated, the agent stops the search and goes back to the node it occupied at the beginning of the search. The return value of CDFS(l, b) is a couple (n, T ). The first term n is an integer such that b -n is the number of distinct edges that have been traversed during the execution of CDFS(l, b). If the bound b has been respected then n ≥ 0, otherwise n = -1. Concerning the second term T of the return value, it simply corresponds to the resulting DFS tree of the execution of CDFS(l, b). If n ≥ 0 and v is the occupied node at the start of CDFS(l, b), then for every node u such that d T (u, v) < l, u is complete in M at the end of CDFS(l, b).

Algorithm 5 : 3 Mark node v; 4 while 5 pt 1 : 6 Take port pt 1 ; 7 w 8 pt 2 : 9 if v < w then 10 K 12 K 13 M

 5345167829101213 CDFS(l, b)1 v := the current node; T := ({v}, ∅); bound := b; 2 if l > 0 then node v is incomplete in M and bound ≥ 0 do = the smallest free port at node v in M; := the current node; = the port by which the agent has just entered node w; := ({v, w}, {(v, w, pt 1 , pt 2 )}); 11 else := ({v, w}, {(w, v, pt 2 , pt 1 )}); := M K; bound := bound -1; 14 if w is not marked then 15 (bound, T ) := CDFS(l -1, bound); 16 T := T T K; 17 Take port pt 2 ; 18 Unmark node v; 19 return (bound, T ); The case where l ≥ 2 and m =⊥ in Algorithm 4 relies on function LocalExpansion. It is exactly here that we make use of the algorithmic technique of [11] mentioned at the end of Section 3, which is based on a set of adequately pruned trees. In our solution, this set corresponds to the variable T . It is a global variable like M and it is initialized to ∅ at the beginning of each call to GlobalExpansion (cf. line 4 of Algorithm 4). Let us consider the ith call LE i to LocalExpansion(l, b) made from node L[i] during an execution of GlobalExpansion(l, m). At the end of LE i , the return value of LocalExpansion(l, b) is an integer n ≥ -1 such that b -n is the number of distinct edges that have been traversed during LE i and that were not in M at the start of LE i . Besides, in the case where n ≥ 0, at the end of LE i we can guarantee that for each incomplete node u of M, d M (L[i], u) > l or u is one of the last |L| -i nodes of L (i.e., a node of L from which the agent has not yet executed LocalExpansion(l, b)).

Algorithm 6 : 3 T 7 Prune(l); 8 bound 12 T

 637812 LocalExpansion(l, b) 1 bound := b; v := the current node; 2 if v is incomplete in M and no tree of T contains node v then := T ∪ {({v}, ∅)}; 4 while IncompleteNodes(v, M, l) ∩ Nodes(T ) = ∅ and bound ≥ 0 do 5 u := the node with the smallest label in IncompleteNodes(v, M, l) ∩ Nodes(T ); 6 MoveTo(M, u); := Explore(l, bound); 9 Remove from T every tree for which all the nodes are complete in M; 10 while there are two trees T and T in T having a common node do 11 T := the spanning tree produced by the BFS traversal of T T from the node having the smallest label in T T ; := (T \ {T, T }) ∪ {T }; 13 Execute in the reverse order all the edge traversals that have been made since the beginning of the current iteration of the while loop; 14 return bound; Let us examine what happens during iteration I. At the beginning of I, the agent follows a path of length at most l from node L[i] to a node u that is incomplete in M (cf. line 5 of Algorithm 6).

Algorithm 8 : 7 ( 8 T

 878 Explore(l, b) 1 bound := b; i := 1; v := the current node; 2 T := the tree of T containing node v; 3 V := array containing all the nodes of T sorted in the order of the first visit through the DFS traversal of T from node v; 4 while i ≤ |V | and bound ≥ 0 do 5 MoveTo(T, V [i]); 6 if node V [i] is incomplete in M then bound, T ) := CDFS( l 2 , bound); := T ∪ {T }; 9 return bound;

Lemma 5 . 1

 51 Consider an execution E of function CDFS(l, b) from a node u of G where l ≥ 1 and b ≥ 0 are integers. Assume that M 1 (E) ⊆ G. Execution E terminates at node u, and the agent always knows a path of length at most l from node u to its current node during E. Lemma 5.2 Consider an execution E of function CDFS(l, b) from a node u of G where l ≥ 1 and b ≥ 0 are integers. Assume that M 1 (E) ⊆ G. Function CDFS(l, b) returns a couple (i, T r) such that the following properties are satisfied.

  0 and the total cost induced by these calls is 2|G|: in particular, if m =⊥, variable b is equal to m -|G| ≥ -1 at the end of E. Using the same lemma, it follows that all the nodes of L are complete in M 2 (E) if m =⊥, or if m =⊥ and b ≥ 0 at the end of E. Finally, at the beginning and at the end of each move made during each execution of CDFS from a node L[i], the agent knows a path of length at most 1 fromL[i].From Claim 5.1 and the above explanations, it follows that E terminates at node s and during E the agent always knows a path in G of length at most f + 1 from node s to its current node. It also follows that if m =⊥ (resp. m =⊥) the cost of E is O(e(f + 1)) (resp. O(e(f ) + m) as |G| ≤ m + 1). Besides, if m =⊥, or m =⊥ and b ≥ 0 at the end of E, then B f +1 (G, s) = M 2 (E) and the return value of GlobalExpansion(l, m) is true according to line 16 of Algorithm 4. Otherwise, B f (G, s) ⊆ M 2 (E), the return value of GlobalExpansion(l, m) is false, and e(f + 1) > e(f ) + m (since the last value of b is -1 and |B f (G, s) G| = 0, we have |M 1 (E) G| = e(f ) + m + 1). This proves the lemma in the case where l = 1.

  s) H by Claim 5.3. Moreover, M 1 (E) H ⊆ B f +2l-1 (G, s) and |B f (G, s) H| = 0 by Claim 5.3, and |H| > m, which implies that e(f + 2l -1) > e(f ) + m.

Claim 5 . 1 2

 51 10 If |S| ≥ 2, the cost of E 0 is O(e(f )). By Lemma 5.3 and Claim 5.8, E 1 terminates and its cost is O(m), which is O(e(f )) as m = e(f ), M 1 (E) = B f +1 (G, s) and e(f + 1) < 2m. If GlobalExpansion(l 0 , m) returns true in E 1 , we know that |S| = 2 in view of the condition of the while loop of Algorithm 3. Since the cost of E 0 is O(e(f )) (cf. Claim 5.10), the total cost of S (and thus of E) is O(e(f )). Moreover, f loor 1 = f loor 0 + l 0 = f + 1 + xf -which is more than (1 + x 3 )f , as xf ≥ 3. Hence, at the end of S the second property is satisfied with f = f loor |S|-1 = f loor 1 . Now, consider the case where GlobalExpansion(l 0 , m) returns false in E 1 . To deal with this case, we need to prove the following claim. Claim 5.11 For every 1 ≤ k ≤ |S| -1, e(ceil k ) > 2e(f ).

2

  edge traversals if S i is made of only one block of αf i 2 edge traversals. Otherwise, it consists in backtracking to node s by executing in the reverse order the last|P k * -1 | + αf i 2 edge traversals where k * = c i αf i 2is the number of blocks of αf i 2 edge traversals in S i .

  As a result, we have the following claim owing to the fact that the nodes of L are sorted in the order of the first visit through the DFS traversal of B f (G, s) from node s, and the fact that the agent always takes the shortest path in the tree produced by this traversal when it executes the move instructions of lines 6 and 15 of Algorithm 4. The total cost induced by the edge traversals belonging to the first or third type in E is O(e(f )). Moreover, at the beginning and at the end of each edge traversal of the first or third type in E, the agent knows a path of length at most f from node s to its current node. Finally, if l = 1 or if each execution of LocalExpansion in E terminates, then E terminates at node s. If m =⊥, the agent executes CDFS(1, b) also from the nodes of L, but not necessarily all of them if b becomes negative. Let G be the subgraph of G that is explored during the executions of function CDFS, whether m is ⊥ or not. Using Lemma 5.2, it follows by induction on the number of calls to CDFS that M 2

	Claim 5.1

1, deg(L[i])) (resp. CDFS(1, b)) in Algorithm 4 from a node L[i] starts and ends at L[i] according to Lemma 5.1. Also note that if an execution of LocalExpansion from L[i] terminates (this will be shown below), the agent is back at L[i] at the end of this execution in view of line 13 of Algorithm 6. From the above explanations, it follows that for all 2 ≤ i ≤ |L|, the agent is at node L[i -1] when it starts executing the ith iteration of the while loop of Algorithm 4. It also follows that the agent is at node L[|L|] when it starts executing line 15 of Algorithm 4. We first prove the lemma in the easiest case where l = 1. The nodes of L are all at distance at most f from node s in B f (G, s). If m =⊥, the agent executes function CDFS(1, deg(L[i])) from each node L[i].

Time in this conjecture is what we call cost, i.e., the worst-case number of edge traversals until finding the treasure.

Since the treasure has to be hidden in a node, the agent does not necessarily have to traverse all edges of the ball B d (G, s).

Supported in part by NSERC discovery grant 2018-03899 and by the Research Chair in Distributed Computing of the Université du Québec en Outaouais.

2l k -1) > e(f loor k ) + m, which implies e(ceil k+1 ) > 2e(f ) as ceil k+1 = f loor k + 2l k -1 (cf. line 10 of Algorithm 3) and f loor k ≥ f + 1. This completes the inductive proof of the claim.

With the above claim, we are ready to conclude the case where GlobalExpansion(l 0 , m) returns false in E 1 . For every 1 ≤ k ≤ |S| -1, the cost of E k is equal to the cost of the execution of GlobalExpansion(l k-1 , m), which is O(e(f loor k-1 ) + m) by Lemma 5.3 and Claim 5.8. Besides, m = e(f ) and e(f loor k-1 ) < 2m for every 1 ≤ k ≤ |S| -1 (by the condition of the while loop of Algorithm 3). Thus, from Claims 5.9 and 5.10, the cost of S is O(e(f ) log(f + 2)). Since E |S|-1 corresponds to the last iteration of the while loop, we get l |S|-1 < 1 or e(f loor |S|-1 ) ≥ 2m (M 2 (E |S|-1 ) = B f loor |S|-1 (G, s) by Claim 5.8). Note that from lines 7 to 10, it follows that ceil |S|-1 -

) ≥ 2m and we have e(f loor |S|-1 + 1) ≥ 2e(f ) because m = e(f ). As a result, the third property of the lemma is satisfied with f = f loor |S|-1 . This completes the analysis of the case where GlobalExpansion(l 0 , m) returns false in E 1 , and thus concludes the proof of this lemma.

If we put aside the initial assignments of lines 1 and 2 in Algorithm 2, the execution of procedure TreasureHunt(x) from the source node s in G can be viewed as a sequence of consecutive executions of procedure Search(x): the ith execution of Search(x) in this sequence will be denoted by S i .

The following lemma is a small technical observation concerning the execution of TreasureHunt(x) from the source node s. Since, at the beginning of this execution, variable M is equal to B 0 (G, s), the lemma can be easily proved by induction on i using Lemma 5.4. Lemma 5.5 Consider an execution of procedure TreasureHunt(x) from the source node s, for any real constant x > 0. For every integer i ≥ 1, S i starts and ends at node s, and there are two integers

We are now ready to prove the main result of this section that is stated in the following theorem.

Theorem 5.1 Consider a graph G of unknown radius r in which a treasure is located at an unknown distance at most 1 < d ≤ r from the starting node s of an agent. For any real constant x > 0, procedure TreasureHunt(x) allows the agent to find the treasure at cost O(e(d) log d).

Proof. Let S = (S 1 , S 2 , S 3 , . . .) be the sequence of consecutive executions of Search(x) resulting from the execution of procedure TreasureHunt(x) from node s. The length of S, i.e., the number of executions of Search(x) in S, will be denoted by |S| (we show below that |S| is upper bounded by d). According to the procedure, the sequence S is interrupted as soon as the treasure is found during some execution S i , which means that S i is interrupted before its "natural end". Nonetheless, to simplify the subsequent discussions, we will suppose in this proof that, instead of stopping as soon as the treasure is found, the agent stops at the end of the first execution of Search(x) during which it has found the treasure. Hence, all the executions of Search(x) in S are complete. So, assume that at the beginning of the kth interruption, the agent does not know a path of length at most f i from node s to node u k . In view of the fact that D k ≤ f i + 1, the shortest path from node s to node u k that is known by the agent has actually length exactly f i + 1. Before explaining what the agent does, let us give some properties that necessarily hold in this situation. We have the following claim. Claim 6.2 e k belongs to G i-1 or to the sequence (e 1 , e 2 , . . . , e k-1 ).

Proof of the claim. Suppose by contradiction that the claim does not hold. Let G * be the graph G with a midpoint z added on edge e k and denote by S * i the ith call to Search( α 2 ) made during an execution of TreasureHunt( α2 ) from node s in G * . Note that, in view of the execution of TreasureHunt( α2 ) in G, the definition of G * and the assumption that the claim does not hold, S * i indeed exists and at the beginning of

We know that just before making its kth edge traversal during S i , the agent is at node u k and the shortest path that is known by the agent from node s to node u k in G has length exactly f i + 1. Hence, the definition of G * and the fact that e k does not belong to G i-1 or to the sequence (e 1 , e 2 , . . . , e k-1 ), implies that during S * i , there is a time t when the agent is at z and the shortest path that is known by the agent from node s to z in G * has length exactly f i + 2. However, by Lemma 5.4, the length of the shortest path that is known by the agent from node s to z in G * at time t must have length at

. This is a contradiction, which proves the claim.

From the above claim, it follows that at the beginning of the kth interruption the agent has already traversed edge e k before, and already knows which edge of G i-1 or of (e 1 , e 2 , . . . , e k-1 ) corresponds to it. Thus, at the beginning of the kth interruption, the agent can already determine a path of length at most f i + 1 from node s to node u k+1 because in view of Lemma 5.4 it must know such a path when reaching node u k+1 and because the traversal of e k does not bring extra topological information on G. Now we are are able to formulate what the agent does, when it has noticed that it does not know a path of length at most f i from node s to node u k . It executes in the reverse order the last D k edge traversals, at the end of which it is at node s and Sk is empty. Then, instead of coming back to u k , it goes directly to node u k+1 using the known path (highlighted in the previous paragraph) of length at most f i + 1 from node s to node u k+1 . Once this is done, the interruption is over: the agent resumes S i and acts as if it had just traversed edge e k (as previously mentioned, it just performs some computations before interrupting again S i for the next edge traversal, if any). It follows that at the end of the interruption, and thus at the beginning of the following one if any, H(k + 1) is satisfied. We have shown by induction on k that, at the beginning of the kth interruption, for any k ≥ 1, the property H(k) is satisfied. This closes the description of the interruptions.

It remains to deal with the close period. At the beginning of it, property H(c i + 1) is satisfied, which implies that the agent has performed D c i +1 ≤ f i + 1 edge traversals since the last time when Sk was empty. Hence, during the close period, the agent simply executes in the reverse order the last D c i +1 edge traversals, at the end of which Sk is empty. In view of this, of the fact that Sk is empty at the beginning of S i , and of property H(c i + 1), the frequent return property is satisfied