Ralf Klasing
email: ralf.klasing@labri.fr

Euripides Markou
email: emarkou@softlab.ece.ntua.gr

Tomasz Radzik
email: tomasz.radzik@kcl.ac.uk

Fabiano Sarracco
email: fabiano.sarracco@dis.uniroma1.it

Approximation bounds for Black Hole Search problems

Keywords: Approximation algorithm, black hole search, graph exploration, mobile agent, inapproximability

. We also prove APX-hardness for a restricted version of the problem, in which only the starting node is initially known to be safe.

Introduction

The Background and the Problem. The problem of protecting mobile agents from malicious hosts, i.e., nodes of a network which store harmful processes in them, has been widely studied [START_REF] Hohl | Time limited black box security: Protecting mobile agents from malicious hosts[END_REF][START_REF] Hohl | A framework to protect mobile agents by using reference states[END_REF][START_REF] Ng | Protecting mobile agents against malicious hosts by intention of spreading[END_REF][START_REF] Sander | Protecting mobile agents against malicious hosts[END_REF]. Even though various countermeasures have been proposed, the general belief (see [START_REF] Hohl | Time limited black box security: Protecting mobile agents from malicious hosts[END_REF][START_REF] Schelderup | Mobile agent security -issues and directions[END_REF]) is that it is very hard (if not virtually impossible) to fully protect mobile agents from malicious hosts attacks.

We consider here malicious hosts of a particularly harmful nature, called black holes [START_REF] Czyzowicz | Complexity of searching for a black hole[END_REF][START_REF] Czyzowicz | Searching for a black hole in tree networks[END_REF][START_REF] Dobrev | Black hole search in common interconnection networks. Networks, pages 169-180[END_REF][START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF][START_REF] Dobrev | Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. Distributed Computing[END_REF]. A black hole is a node in a network which contains a stationary process destroying all mobile agents visiting this node, without leaving any trace on the other nodes of the network. Since agents cannot prevent being annihilated once they visit a black hole, the only way of protection against such processes is identifying the hostile nodes and avoiding further visiting them. In order to locate a black hole, at least one agent must visit it. However, no hint about the presence of a black hole can be deduced by visiting its neighborhood, and it is also assumed that an agent visiting a black hole has no way of communicating with other agents before being terminated. Therefore, it should be clear that it is possible to locate a black hole only by "sacrificing" one agent and by using another agent to indirectly infer the existence of a black hole. An agent which is to visit an unknown node can, for instance, have a meeting scheduled with another agent after such visit, or write on a white-board in a neighboring node the label of the unknown node that he is visiting. If the visited node is a black hole, then the destroyed agent will neither turn up at the node where the meeting was scheduled nor write back to the white-board that the node has been successfully visited. In both cases, the surviving agents can deduce that the visited node is a black hole.

In this paper, we investigate the case when there may be at most one black hole in the network, and the search is performed by exactly two agents, which start from the same node s and can communicate only when they are in the same node. At least one agent must report back to s the information on where exactly the black hole is or that there is none. We consider the problem of designing a black hole search scheme for a given network, a given starting node s, and a given subset S ⊇ {s} of nodes which are initially known to be safe. The black hole, if present, may be at any node not in S.

The issue of efficient black hole search was extensively studied in [START_REF] Dobrev | Black hole search in common interconnection networks. Networks, pages 169-180[END_REF][START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF][START_REF] Dobrev | Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. Distributed Computing[END_REF] under the scenario of totally asynchronous networks, i.e., while every edge traversal by a mobile agent requires finite time, there is no upper bound on this time. To solve the problem in this setting, the network must be 2-connected. Moreover, in an asynchronous network it is impossible to answer the question of whether a black hole actually exists, hence it is assumed in [START_REF] Dobrev | Black hole search in common interconnection networks. Networks, pages 169-180[END_REF][START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF][START_REF] Dobrev | Searching for a black hole in arbitrary networks: Optimal mobile agents protocols. Distributed Computing[END_REF] INRIA that there is exactly one black hole and the task is to locate it. Due to the asynchronous setting, there is no obvious and interesting measure of the time needed by the agents to find the black hole. Hence, the complexity measure considered is the total number of moves performed by the agents. For arbitrary networks of n nodes, the authors show that Θ(n log n) moves are necessary and sufficient.

In this paper, we study the problem under the scenario of synchronous networks, previously considered in [START_REF] Czyzowicz | Complexity of searching for a black hole[END_REF][START_REF] Czyzowicz | Searching for a black hole in tree networks[END_REF][START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF]. In this scenario there is an upper bound on the time needed by an agent for traversing any edge. This assumption makes a dramatic change to the problem. The black hole can be located by two agents in any network and moreover the agents can decide if there is a black hole or not. To measure the efficiency of a black hole search, it is assumed that each agent takes exactly one time unit (one synchronized step) to traverse one edge (and to make all necessary computations associated with this move). Then the cost of a given black hole search (scheme) is defined as the total number of time units the search takes under the worst-case location of the black hole in the network, or when the network contains no black hole.

The running time of an algorithm producing a black hole search scheme should be distinguished from the cost (the worst-case time) of the search based on this scheme. Informally, the former is the time of preparing (planning) the walk, while the latter is the time of walking. Here, we study the optimization problem of computing a minimum-cost black hole search scheme for a given network, a given starting node and a given set of nodes initially known to be safe. From now on, the Black Hole Search problem refers to this optimization problem.

Previous Results. In [START_REF] Czyzowicz | Complexity of searching for a black hole[END_REF] the authors prove that the Black Hole Search problem is NPhard, and show a 9.3-approximation algorithm for it. The restricted case of this problem, when the starting node is the only node initially known to be safe (S = {s}), is considered in [START_REF] Czyzowicz | Searching for a black hole in tree networks[END_REF][START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF]. In [START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF] the authors prove that this restricted case is also NP-hard, and give a Our Results. We show that the Black Hole Search problem is not approximable in polynomial time within a 1 + ε factor for any ε <1 388 , unless P=NP. Moreover, we give a 6-approximation algorithm for this problem, i.e., a polynomial time algorithm which, for any input instance, produces a black hole search scheme with cost at most 6 times the best cost of a black hole search scheme for this input. This improves on the 9.3-approximation algorithm shown in [START_REF] Czyzowicz | Complexity of searching for a black hole[END_REF]. Finally, we prove that the restricted case in which only the starting node is initially known to be safe is also APX-hard.

Model and Terminology

We represent a network as a connected undirected graph G = (V, E), where nodes denote hosts and edges denote communication links. 1 With no loss of generality, we assume that G has no multiple edges or self-loops.

The two agents, called Agent-1 and Agent-2, start the black hole search from a START-ING NODE s ∈ V and explore graph G by traversing its edges. Together with the starting node s, a subset of nodes S which are initially known to be safe is given. Let U = V \ S, and let B ⊆ U denote the (unknown) location of the black hole, with either B = ∅ or B = {b}. We formalize the general version of the Black Hole Search problem (set S can be any proper subset of V including s) in the following way.

(General) Black Hole Search problem (BHS problem)

Instance : a connected undirected graph G = (V, E), a subset of nodes S ⊂ V and a node s ∈ S. Solution : a feasible EXPLORATION SCHEME E G,S,s = (X, Y) for (G, S, s), where X = x 0 , x 1 , . . . , x T and Y = y 0 , y 1 , . . . , y T are two equal-length sequences of nodes in G. The feasibility of E G,S,s is determined by constraints 1-4 given below. The length of E G,S,s is defined to be T . Measure : the cost of the Black Hole Search (BHS) based on E G,S,s (defined below). Goal : minimization.

When the BHS based on a given exploration scheme E G,S,s is performed in G, Agent-1 follows the path defined by X while Agent-2 follows the path defined by Y. At the end of the i-th step of the search (at time i), Agent-1 is in node x i while Agent-2 is in node y i . As soon as an agent deduces the value of B, it "aborts" the exploration and returns to the starting node s by traversing nodes in V \ B.

If X = x 0 , x 1 , . . . , x T and Y = y 0 , y 1 , . . . , y T are two equal-length sequences of nodes in G, then E G,S,s = (X, Y) is a feasible exploration scheme for the input (G, S, s) (and can be effectively used as a basis for a BHS in G) if the constraints 1-4 stated below are satisfied.

Constraint 1: x

0 = y 0 = s, x T = y T .
Constraint 2: for each i = 0, . . . , T -1, either x i+1 = x i , or (x i , x i+1 ) ∈ E; and similarly either y i+1 = y i or (y i , y i+1 ) ∈ E.

Constraint 3: U ⊆ T i=0 {x i } ∪ T i=0 {y i }.
Constraint 1 corresponds to the fact that both agents start from the given starting node s. The requirement that the sequences X and Y end at the same node provides a convenient simplification of the reasoning without loss of generality. Constraint 2 models the fact that during each step, each agent can either WAIT in the node v where it was at the end of the previous step, or traverse an edge of the network to move to a node adjacent to v. Constraint 3 assures that each node in U is visited by at least one agent during the exploration. We need additional definitions to state Constraint 4.

Given an exploration scheme E G,S,s = (X, Y), for each i = 0, 1, . . . , T , we call the EXPLORED TERRITORY at step i the set S i defined in the following way:

S i = S ∪ i j=0 {x j } ∪ i j=0 {y j } , if x i = y i ; S i-1 ,
otherwise.

Thus S 0 = S by Constraint 1, S T = V by Constraint 1 and Constraint 3, and S j-1 ⊆ S j for each step

1 ≤ j ≤ T . A node v is EXPLORED at step i if v ∈ S i , or UNEXPLORED
otherwise. An unexplored node v may have been already visited by one of the agents, but it will become explored only the next time the agents meet and communicate; recall that the agents communicate with each other, exchanging their full knowledge, when and only when they meet at a node. If both agents are alive at the end of step i, then the explored nodes at this step are all nodes which are known to both agents to be safe. Note that the explored territory is defined for an exploration scheme E G,S,s , not for the BHS based on E G,S,s , and does not take into account the possible existence of the black hole. This is taken into account in the definition of the cost of the BHS based on E G,S,s . A MEETING STEP (or simply MEETING) is the step 0 and every step 1 ≤ j ≤ T such that S j = S j-1 . Observe that, in each meeting step j, the agents must be in the same node (x j = y j ), which we call a MEETING POINT. Note that the opposite is not necessarily true, i.e., there can exist non-meeting steps during which the agents are in the same node. For example, the agents could be following together a path of already explored nodes to get to a new part of the network. They would be at the same time in the same nodes, but would not be increasing the explored territory. The meeting steps are the steps when the agents meet and add at least one new node to the explored territory. A sequence of steps j + 1, j + 2, . . . , k where steps j and k are two consecutive meetings is called a PHASE of length kj. We give now the last constraint on a feasible exploration scheme. Constraint 4(a) means that during each phase, one agent can visit at most one unexplored node. If it visited two or more unexplored nodes and one of them was a black hole, then the other, surviving, agent would not know where exactly the black hole is. Constraint 4(b) says that the same unexplored node cannot be visited by both agents during the same phase, or otherwise they both may end up in a black hole (see [START_REF] Czyzowicz | Searching for a black hole in tree networks[END_REF] for a more detailed discussion). From now on an exploration scheme means a feasible exploration scheme.

For an exploration scheme E G,S,s = (X, Y) and a subset B of unexplored nodes (with |B| ≤ 1), the EXECUTION TIME is defined as the number of time units needed to perform the BHS based on E G,S,s , in the case that B is the set of black holes. If B = ∅, then the execution time is equal to the length T of the exploration scheme, plus the shortest path distance from x T (= y T ) to s. In this case the agents must perform the full exploration (spending one time unit per step) and then get back to the starting node to report that there is no black hole in the network. If B = {b} ⊆ U , then let j be the first step in E G,S,s such that b ∈ S j . Observe that j must be a meeting step and 1 ≤ j ≤ T , since S 0 = S and S T = V . The execution time in this case is equal to j plus the length of the shortest path from x j (= y j ) to s not including b. In this case one agent, say Agent-1, vanishes into the black hole during the phase ending at step j, so it does not show up to meet Agent-2 at node x j = y j . Since, by Constraint 4(a), Agent-1 has visited only one unexplored node during the phase (node b), and, by Constraint 4(b), Agent-2 has not visited that node, the surviving Agent-2 learns the exact location of the black hole and thus it goes back to s, obviously omitting the black hole.

The COST of the BHS based on an exploration scheme E G,S,s = (X, Y) is denoted by cost(E G,S,s ) and defined as the worst (maximum) execution time of E G,S,s over all possible values of B (including B = ∅).

We recall from [START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF] the next two simple observations. Lemma 1. If step k ≥ 1 is a meeting step for an exploration scheme E G,S,s , then

x k = y k ∈ S k-1 .
Proof. Let j be the last meeting step before step k, and hence

S j = S j+1 = . . . = S k-1 . By definition x k = y k ∈ S k . If x k = y k is not in S k-1
, then it is in both {x j+1 , . . . , x k }\S j and {y j+1 , . . . , y k } \ S j . In this case, at least one of the conditions of Constraint 4 is violated, since either the two sets are the same or at least one of the two contains more than one node.

INRIA Lemma 2. Each phase of an exploration scheme E G,S,s has length at least 2.

Proof. Let us suppose, by contradiction, that there exists in E G,S,s a phase of length 1, and hence two adjacent meeting steps j and j + 1. The step j + 1 is a meeting if and only if S j+1 S j , but, by Lemma 1, x j+1 = y j+1 ∈ S j , and hence S j+1 = S j . Therefore there cannot exist in E G,S,s a phase of length 1.

Phases of length 2 which expand the explored territory by 2 nodes are of particular interest to us since they advance the exploration of the network at the fastest possible rate. Any phase j + 1, j + 2 of this kind has to have the following structure. Let m be the meeting point at step j. During step j + 1, Agent-1 visits an unexplored node v 1 adjacent to m, while Agent-2 visits an unexplored node v 2 adjacent to m as well, and v 1 = v 2 . In step j + 2, the agents meet in a node which has been already explored and is adjacent to both v 1 and v 2 . This node can be either m, and in this case we denote the phase as b-split(m, v 1 , v 2 ), or a different node m = m, and in this case we denote the phase as a-split(m, v 1 , v 2 , m ).

The following lemma helps to simplify, at least in some cases, the computation of the cost of the BHS based on a given exploration scheme. Lemma 3. Let (G, S, s) be an input instance for the BHS problem problem, and let U be the set of initially unexplored nodes (U = V \ S). The case B = ∅ yields the maximum execution time for any exploration scheme in (G, S, s) if, by removing any node u ∈ U from G, each node in V \ {u} either becomes disconnected from s, or maintains its shortest path distance from s.

Proof. Let us consider any exploration scheme E G,S,s and the case B = {b} = ∅ (for any b). By hypothesis, we can remove b from G and have a partition of the nodes in two subsets: nodes becoming disconnected from s, and nodes maintaining the distance from s. The meeting point m at the end of the phase of E G,S,s during which b is visited for the first time must be in this latter subset. Therefore, the path from m to s defined in E G,S,s for the case B = ∅ cannot be shorter than the shortest path from m to s the surviving agent can follow in the case B = {b}. Corollary 1. Let (G, S, s) be an input instance for the BHS problem. If G is a tree rooted at s, then the case B = ∅ yields the maximum execution time for any exploration scheme in (G, S, s).

Proof. This assertion straightforwardly follows from the property that in any tree there is always a unique path from any node to the root.

Note that in our model we do not account for the time of computing the shortest path that the surviving agents are to follow to return to s at the end of the exploration. We assume that either this time is negligible or the whole set of required shortest paths is pre-computed and stored in the agents' memory.

Approximation Lower Bound for the General BHS Problem

In this section, we provide an explicit lower bound on the approximability of the General Black Hole Search problem by showing an approximation preserving reduction from a particular subcase of the Traveling Salesman Problem, presented in [START_REF] Engebretsen | TSP with bounded metrics: stronger approximation hardness[END_REF]. For a constant integer M , TSP(1,M) is defined in the following way.

TSP(1,M)

Instance : a pair (G, d), where G = (V, E) is a complete graph (with V = {v 1 , . . . , v n })
and d : V 2 → {1, . . . , M } is a distance function associating to each pair of nodes (v, u) a positive integer length d(v, u) between 1 and M (where

M is a constant). Function d is symmetric (i.e., d(u, v) = d(v, u)
) and satisfies the triangle inequality (i.e., d(i, j)

+ d(j, k) ≥ d(i, k), ∀i, j, k ∈ V ). Solution : a tour τ of G, i.e., a permutation τ = v π(1) , v π(2) , . . . , v π(n) of the nodes in V .
We assume that π(n + 1) = π(1) = 1. Measure : the length (or cost) of the tour, i.e.,

cost(τ ) = n i=1 d(v π(i) , v π(i+1) ).
Goal : minimization. Lemma 4. [START_REF] Engebretsen | TSP with bounded metrics: stronger approximation hardness[END_REF] It is NP-hard to approximate TSP(1,8) within 1 + ε for any ε < 1 388 .

Our approach to prove the APX-hardness of the BHS problem is the following. We first provide a reduction from instances (G, d) of TSP(1,M) to instances (G , S, s) of the BHS problem. Given a solution τ for an instance (G, d) of the first problem, we construct a solution E τ G ,S,s for the corresponding instance (G , S, s) of the BHS problem. We show that cost(E τ G ,S,s ) = 2cost(τ ) (Lemma 7). Then, by introducing the concept of regular exploration schemes, we show that given any exploration scheme E G ,S,s , we can find a tour τ in G such that cost(E τ G ,S,s ) ≤ cost(E G ,S,s ) (Lemma 11 and Lemma 12). Finally, we show that if, for any instance of the BHS problem constructed by reduction from an instance of TSP(1,M), we can approximate the optimal solution within a (1 + ε) factor, then we can INRIA approximate the optimal solution of the corresponding instance of TSP(1,M) within the same factor (Lemma 13).

Reduction from instances (G, d) of TSP(1,M) to instances (G , S, s) of the BHS problem. Let (G, d) be an instance of TSP(1,M). We define the graph G = (V , E ), the set S ⊂ V , and the starting node s, in the following way. Recall that V = {v 1 , v 2 , . . . , v n }. We begin the construction with V = {v 1 }, S = ∅ and define s = v 1 as the starting point of the BHS. For each node v i (2 ≤ i ≤ n) in V , we add to V a pair of nodes v i , v i . We refer to node v 1 as the ISLAND I 1 , and to each pair of nodes v j , v j (with j = 2, . . . , n) as the ISLAND I j . For each edge

(v i , v j ) in E of length d(v i , v j ), we add to G a path of 2 • d(v i , v j ) -1 new
nodes, and edges connecting one endpoint of this path to nodes v i and v i (or v 1 , if i = 1) and the other to nodes v j and v j (or v 1 if j = 1). We denote such path connecting island I i with island I j as BRIDGE i ↔ j. We add all the nodes of the bridge to S. We call as b i,j and as b j,i the endpoints of bridge i ↔ j adjacent respectively to island I i and island

I j (note that if d(v i , v j ) = 1, then b i,j ≡ b j,i ).
Observe that each bridge is composed of at least one (safe) node, and that |V \ S| = 2(n -1). An example of this reduction is presented in Figure 1.

Lemma 5.

The distance in G between any node of island I i and any node of island I j (where i = j and i

, j = 1, . . . , n) is equal to 2 • d(v i , v j ). Proof. By construction, bridge i ↔ j is composed of 2•d(v i , v j )-1 nodes.
Hence the length of the path from I i to I j which uses such bridge is 2 • d(v i , v j ). Suppose, by contradiction, that there exists a path in G from I i to I j of length less than 2 • d(v i , v j ). This path starts from I i , visits some other islands (say I k 1 , . . . , I k k ) and then ends in

I j . The length of such path is 2 [d(v i , v k 1 ) + d(v k 1 , v k 2 ) + • • • + d(v k k , v j )]. This would mean that d(v i , v k 1 ) + d(v k 1 , v k 2 ) + • • • + d(v k k , v j ) < d(v i , v j )
. By triangle inequality on the distances in G, this is not possible. Contradiction.

The following lemma gives a useful property of the constructed instance (G , S, s) of the BHS problem. Lemma 6. For any exploration scheme for the constructed instance (G , S, s) of the BHS problem, the case B = ∅ yields the maximum execution time.

Proof. Let v i be any node in U . By removing v i from G , no node becomes disconnected from s. Moreover, the node v i (the other unexplored node in the same island), is at the same distance as v i from s, and has exactly the same set of neighbors as v i . Therefore, each node INRIA in G which has v i in his shortest path to s, can replace v i with v i in the path and remain at the same distance from s. By Lemma 3 the assertion is proved.

!" !# !$ !% ! " # # " # !" !& # !' # !' $ !& $ !& % !' % !"( $% &% ) #*$ ) $*#
Having a mapping from the instances of TSP(1,M) to instances of the BHS problem, we define now a mapping from the solutions for an instance of the TSP(1,M) problem to solutions of the corresponding instance of the BHS problem. Given an instance (G, d) of TSP(1,M), a corresponding instance (G , S, s) of the BHS problem, and a tour τ in G, we define an exploration scheme on G which explores the islands in G in the order defined by τ . In the following definition we introduce a new term: walk. By walk(b) we mean that both agents, which are supposed to be currently in the same node w, move to b by following a shortest safe path from w to b. Observe that such a walk is not a complete phase (no new nodes are explored), but we use it as the initial part of a phase.

Let τ = v π(1) , v π(2) , . . . , v π(n) be a tour on G of length l. Recall that we assume π(n + 1) = π(1) = 1, and that node b i,j is the node adjacent to I i on the bridge i ↔ j. A τ -BASED EXPLORATION SCHEME E τ G ,S,s on G consists of the following sequence of steps:

1. walk(b 1,π(2) ); 2. for each i = 2, . . . , n: (a) walk(b π(i),π(i-1) ); (b) a-split(b π(i),π(i-1) , v π(i) , v π(i) , b π(i),π(i+1) ).
In other words, the two agents walk together along the bridges, then they separate to visit the two nodes of each unexplored island, and finally meet again on the first node of the next bridge.

Given the tour τ in G, the τ -based exploration scheme E τ G ,S,s can be obviously constructed in linear time.

The following lemma gives the cost of the BHS based on E τ G ,S,s . Lemma 7. Given a tour τ = v π(1) , v π(2) , . . . , v π(n) on G of length l, the τ -based exploration scheme E τ G ,S,s satisfies cost(E τ G ,S,s ) = 2 • l. Proof. By Lemma 6, we can compute cost(E τ G ,S,s ) as the execution time of E τ G ,S,s in the case B = ∅. The walk in (1) requires 1 step. For the i-th iteration in (2) (i = 2, . . . , n):

-the walk in (2.a) requires 2 • d(v π(i-1) , v π(i) ) -2 steps; -the split defined in (2.b) requires 2 steps.
The exploration scheme E τ G ,S,s ends in b π(n),1 , and hence the agents have to get back to s.

By Lemma 5, the distance from b π(n),1 to s is 2 • d(v π(n) , v 1 ) -1, therefore: cost(E τ G ,S,s ) = 1 + 2 n i=2 d(v π(i-1) , v π(i) ) + 2 • d(v π(n) , v 1 ) -1 = 2 • l. RR n°6185
Corollary 2. Let (G, d) be an instance of the TSP(1,M) problem, and let (G , S, s) be the corresponding instance of the BHS problem. Let τ * be an optimal solution for (G, d) and let E * G ,S,s be an optimal solution for (G , S, s). Then cost(E * G ,S,s ) ≤ 2 • cost(τ * ).

Proof. Lemma 7 implies

2cost(τ * ) = cost(E τ * G ,S,s ) ≥ cost(E * G ,S,s ).
In what follows, we show a method to modify an exploration scheme without altering its properties (i.e., feasibility, length, sequence of explored territories and the cost of the BHS based on it). We then define a notion of equivalence between exploration schemes which is based on such operation. Definition 1. Let E G,S,s = (X, Y) be an exploration scheme for (G, S, s), and let φ = (X φ , Y φ ) be a phase in E G,S,s . Let E G,S,s be the exploration scheme obtained from E G,S,s by swapping the paths of the two agents in phase φ, i.e., phase φ is replaced by phase φ = (Y φ , X φ ). We call this operation a PHASE-SWAP. Two exploration schemes are EQUIV-ALENT if and only if one is obtained from the other by applying a finite sequence of phaseswaps.

The following lemma is a direct consequence of Definition 1. Lemma 8. Let E G,S,s = (X, Y) be an exploration scheme for (G, S, s). Let E G,S,s be the exploration scheme obtained from E G,S,s by applying a phase swap on E G,S,s . Then, the exploration scheme E G,S,s is feasible, has exactly the same meeting points, the same sequence of explored territories and the same length as E G,S,s . Moreover, cost(E G,S,s ) = cost(E G,S,s ). Corollary 3. Two equivalent exploration schemes have exactly the same meeting points, the same sequence of explored territories and the same length. Moreover the cost of the BHS based on them is the same.

We now turn back our focus to instances (G , S, s) constructed by reduction from instances (G, d). We give a classification of each phase of any exploration scheme in G . A phase φ is a: 2s-phase : if the two nodes of the same island are explored during φ; 2d-phase : if two nodes in two distinct islands are explored during φ;

INRIA 1-phase : if only one node (of one island) is explored during φ. Definition 2. Given an exploration scheme E G ,S,s , we define as PHASE GRAPH of E G ,S,s , the following directed multigraph P (E G ,S,s ). The graph P (E G ,S,s ) has the nodes v 2 , . . . , v n corresponding to the islands I 2 , . . . , I n in G , plus one further node which we call x. The following edges are added to P (E G ,S,s ):

-a directed edge v i , x is added for each node in island I i which is explored during a 1-phase by Agent-1; -a directed edge x, v i is added for each node in island I i which is explored during a 1-phase by Agent-2; -a directed edge v i , v j is added for each 2d-phase exploring a node of island I i with

Agent-1 and a node of island I j with Agent-2; -a directed self-loop v i , v i is added if the nodes of island I i are explored by a 2s-phase. Lemma 9. Given any exploration scheme E G ,S,s , each node of the phase graph P (E G ,S,s ) other than node x has degree (the in-degree plus the out-degree) equal to 2.

Proof. It follows from Definition 2 that, for any node v i in P (E G ,S,s ), there is an outgoing edge for each node in I i of G which is explored by Agent-1, and there is an incoming edge for each node in I i of G which is explored by Agent-2. Since each island I i (i = 2, . . . , n) has two unexplored nodes, the statement follows.

Thus, for the graph P (E G ,S,s ), all edges of the underlying undirected multigraph form edge-disjoint simple cycles. Now, we give a new characterization of an exploration scheme in G . Definition 3. An exploration scheme E G ,S,s is REGULAR if and only if each agent explores exactly one node of each island I j , with j = 2, . . . , n.

Notice that any τ -based exploration scheme is regular; we can observe that each node in P (E τ G ,S,s ) is an isolated node (the only adjacent edge is a self-loop). Indeed, we can prove a tighter relation between regular exploration schemes and their corresponding phase graph.

Lemma 10. An exploration scheme E G ,S,s is regular if and only if, in the corresponding phase graph

P (E G ,S,s ), for each node v i , indeg(v i ) = 1 and outdeg(v i ) = 1.
Proof. By Lemma 9, any node v i in P (E G ,S,s ) has degree 2. Hence, three cases may occur: 1. indeg(v i ) = 1 and outdeg(v i ) = 1: in this case one node of island I i is explored by Agent-1 (the outgoing edge) and the other one is explored by Agent-2 (the incoming edge). Therefore, the island is explored in the regular way.

2. indeg(v i ) = 0 and outdeg(v i ) = 2: in this case both nodes of I i are explored by Agent-1; the island is not explored in the regular way. 3. indeg(v i ) = 2 and outdeg(v i ) = 0: in this case both nodes of I i are explored by Agent-2; the island is not explored in the regular way.

Lemma 11. For any exploration scheme E G ,S,s , there is an equivalent regular one that can be found in linear time.

Proof. It suffices to prove that we can find in linear time a finite sequence of phase-swaps in E G ,S,s , which transforms E G ,S,s into a regular exploration scheme. By Lemma 10, this means transforming P (E G ,S,s ) into a graph where, for each node v i , indeg(v i ) = 1 and outdeg(v i ) = 1. We can observe that each phase-swap in E G ,S,s changes the orientation of the corresponding edge in P (E G ,S,s ). For each (undirected) cycle in P (E G ,S,s ), we change the orientation of some edges to obtain a directed cycle, and thus make regular the graph P (E G ,S,s ), and the corresponding exploration scheme.

Lemma 12. Given an exploration scheme E G ,S,s , we can find in linear time a tour τ on (G, d) such that, for the τ -based exploration scheme E τ G ,S,s , cost(E G ,S,s ) ≥ cost(E τ G ,S,s ).

Proof. By Corollary 3 and Lemma 11, we can assume without loss of generality that E G ,S,s is a regular exploration scheme. By regularity, Agent-1 explores a node of each island in G . Let I X = I π(2) , . . . , I π(n) be the sequence of the islands in G in the order they are explored by Agent-1. Let τ be the tour in G corresponding to I X (i.e., τ = v 1 , v π(2) , . . . , v π(n) ), and let l = cost(τ ). We show that the τ -based exploration scheme E τ G ,S,s is such that cost(E G ,S,s ) ≥ cost(E τ G ,S,s ). Consider the BHS based on E G ,S,s in the case when B = ∅. Agent-1 starts from s, visits islands in I X and then gets back to s. By Lemma 5, the length of this tour is at least 2

• l. Thus, cost(E G ,S,s ) is at least 2 • l. By Lemma 7, cost(E τ G ,S,s ) = 2 • l. Therefore, cost(E G ,S,s ) ≥ cost(E τ G ,S,s ).
Lemma 13. Let (G, d) be an instance of the TSP(1,M) problem, and let (G , S, s) be the corresponding instance of the BHS problem. Moreover, let τ * be an optimal tour in G, and let E * G ,S,s be an optimal exploration scheme for (G , S, s). Let ε > 0. If one can find in polynomial time an exploration scheme E G ,S,s such that cost(E G ,S,s

) ≤ cost(E * G ,S,s )(1 + ε), then one can find in polynomial time a tour τ in G such that cost(τ ) ≤ cost(τ * )(1 + ε).
Proof. Suppose that, given the instance (G , S, s), we can construct in polynomial time an exploration scheme E G ,S,s such that its cost is at most 1 + ε times the cost of an optimal INRIA exploration scheme. By Lemma 12, we can find a tour τ in G such that for the exploration scheme

E τ G ,S,s , cost(E τ G ,S,s ) ≤ cost(E G ,S,s ) ≤ cost(E * G ,S,s )(1 + ε). Therefore: 2cost(τ ) = cost(E τ G ,S,s ) [by Lemma 7] ≤ cost(E * G ,S,s )(1 + ε) ≤ 2cost(τ * )(1 + ε) [by Corollary 2] . Hence, cost(τ ) ≤ cost(τ * )(1 + ε) .
The main theorem immediately follows from Lemma 4 and Lemma 13.

Theorem 1. The BHS problem is not approximable in polynomial time within a factor of 1 + ε for any ε < 1 388 , unless P=NP.

The Restricted BHS Problem is APX-hard

In this section, we consider the restricted version of the BHS problem in which S = {s}, i.e., the starting point is the only node initially known to be safe (we denote such problem as rBHS problem). We show that the BHS problem with this restriction remains APX-hard.

Note that the input of the rBHS problem is fully specified by providing a graph G and the starting node s. In this section, we will hence use the simpler notation E G,s to refer to an exploration scheme and (G, s) to refer to an instance of the rBHS problem. We will prove APX-hardness of the rBHS problem by showing a reduction from TSP(1,2) which preserves the non-approximability. We first recall Lemma 6.3 from [1]: Lemma 14. [START_REF] Csaba | Approximability of dense and sparse instances of minimum 2connectivity, TSP and path problems[END_REF] Assume we are given an instance of TSP(1,2) on the n-node complete graph G, in the form of the subgraph G of G containing the edges of weight 1. Assume that G has max degree 3. Assume that we know that its minimum cost TSP tour is either of cost n or at least (1 + ε 0 )n, for some fixed ε 0 . Then there exists such a constant ε 0 for which it is NP-hard to decide which of the two cases holds. The claim holds for ε 0 = 1 786 . If G is cubic then the claim holds for ε 0 = 1 1290 . With a small abuse of notation we define the cost of a tour in G as the cost of the corresponding TSP tour in the complete graph G. We show a polynomial-time reduction algorithm A from TSP(1,2) to the rBHS problem, which takes as input an instance G of TSP(1,2), computes an instance (G , s) of the rBHS problem, and has the following property.

Lemma 15. Let 0 < ε < 4 7 ε 0 , let G be an n-node cubic graph (an instance of TSP(1,2)), and let (G , s) be the corresponding instance of the rBHS problem computed by the reduction algorithm A. Then the following two conditions hold.

1. If the optimal cost of a tour in G is equal to n, then the optimal cost of an exploration scheme for (G , s) is at most 7 2 n + 1. 2. There exists n 0 = n 0 (ε 0 , ε) such that for n ≥ n 0 , if the optimal cost of a tour in G is at least n(1 + ε 0 ), then the optimal cost of an exploration scheme for (G , s) is greater than 7 2 n + 1 (1 + ε).

This lemma implies that for 0 < ε < 4 7 ε 0 and n ≥ n 0 , if we have an n-node cubic graph G and we know that the optimal cost of a tour in G is either equal to n or at least n(1 + ε 0 ), then we can decide which of these two cases happens, if we have a (1 + ε)-approximation of the optimal cost of an exploration scheme for (G , s). Thus, Lemmas 14 and 15 imply the following theorem.

Theorem 2. It is NP-hard to approximate the rBHS problem within a factor 1 + ε for any ε < 1 2258 .

Description of the reduction algorithm A. Let an n-node graph G = (V, E) be the input instance of TSP(1,2). The construction of the instance (G , s) of the rBHS problem is similar to the construction presented in Section 3. The main differences are that here we do not add bridges corresponding to edges of weight 2 and that all nodes but the starting node s are initially unexplored. More precisely, the construction of (G , s) proceeds as follows. We add node v 1 to G and make it the starting node (s ≡ v 1 ). For each node v i in G, 2 ≤ i ≤ n, we add in G a pair of unexplored nodes v i , v i (as before, we denote this pair as island I i ). For each edge (v i , v j ) in G, we put in G an unexplored node b i,j (bridge node), connected to v i , v i (if i > 1), to v j , v j (if j > 1) and to s. If the number of bridge nodes (that is, the number of edges in G) is odd, then we add another unexplored node b s adjacent to s (to ensure that s is adjacent to an even number of unexplored nodes). Note that s is adjacent to all bridge nodes and is not adjacent to any "island" nodes.

Proof of Lemma 15. Let G be an n-node cubic graph. Since G has m = 3 2 n edges, the total number of nodes in G is 7 2 n -1 + odd(m), and all of them but one are initially unexplored. For an integer x, odd(x) is equal to 1, if x is odd, and to 0 otherwise. As in Section 3, we define for a tour τ = v 1 , v π(2) , . . . , v π(n) in G, the exploration scheme E τ G ,s for (G , s), which explores "two-by-two" the nodes of each island in the order I π(2) , . . . , I π(n) . Here, however, the scheme first explores the bridge nodes.

More formally, the scheme E τ G ,s has the following sequence of steps. Note that the first walk operation, for i = 2, has length 1. For each 3 ≤ i ≤ n, the walk operation has length either 0, if nodes v π(i-1) , v π(i) are adjacent in G, or 2, if nodes v π(i-1) , v π(i) are not adjacent in G. Therefore, if the tour τ has cost n + d (that is, contains d edges of weight 2), then the exploration scheme E τ G ,s has length at most:

3 2 n + odd(m) + 1 + 2d + 2(n -1) ≤ 7 2 n + 2d.
The execution time for the case B = ∅ is at most 7 2 n + 2d + 1, since E τ G ,s ends in a bridge node, which is adjacent to s. This is also an upper bound on the cost of the BHS based on E τ G ,s , since Lemma 3 holds for (G , s). If the cost of tour τ is n, then d = 0 and the cost of E τ G ,s is at most 7 2 n + 1, so the first part of Lemma 15 holds. To prove the second part of Lemma 15, we consider an arbitrary exploration scheme E G ,s , and show that if the cost of this scheme is at most ( 72 n + 1)(1 + ε), then there is a tour in G of length less than n(1 + ε 0 ). By using a similar approach as the one described in Section 3, we can find, through a sequence of phase swaps, a regular exploration scheme E G ,s , equivalent to E G ,s , where each agent explores exactly one node of each island I j for j = 2, . . . , n, and cost(E G ,s ) = cost(E G ,s ). We assume by symmetry that scheme E G ,s is such that Agent-1 explores nodes v j , j = 2, . . . , n, and that v π(2) , . . . , v π(n) is the order in which Agent-1 explores these nodes. We consider the tour τ = v 1 , v π(2) , . . . , v π(n) in G. We further assume, also by symmetry of the agents, that Agent-1 explores at least half of the bridge nodes. Thus Agent-1 explores in total at least m/2 + (n -1) nodes. Agent-1 needs at least one step to reach the first unexplored node, then at least two steps to move from one unexplored node to the next unexplored node, and finally at least one step to reach the last meeting point. Therefore, the length of the exploration scheme E G ,s is at least:

2 m 2 + n -1 = 7 2 n + odd(m) -2. (1)
This bound can be derived also in the following way. Let q i denote the number of bridge nodes explored by Agent-1 between the explorations of node v π(i) and node v π(i+1) , for i = 2, . . . , n -1. Let q 1 and q n denote the number of bridge nodes explored by Agent-1 before the exploration of node v π(2) , and after the exploration of node v π(n) , respectively.

We have n i=1 q i ≥ m 2 . Agent-1 needs at least 2q 1 + 1 steps to reach node v π [START_REF] Czyzowicz | Searching for a black hole in tree networks[END_REF] . Then it needs at least 2q i +2 steps to move from node v π(i) to node v π(i+1) , for each i = 2, . . . , n-1. And finally, it needs 2q n + 1 steps to reach the last meeting point. Thus the length of the exploration scheme E G ,s is at least:

(2q 1 + 1) + n-1 i=2 (2q i + 2) + 2q n + 1 ≥ 2 m 2 + 2n -2 = 7 2 n + odd(m) -2. ( 2
)
We will show that for each index i,

2 ≤ i ≤ n -1, such that (v π(i) , v π(i+1)
) is not an edge in G, Agent-1 takes in fact at least 2q i + 4 steps to move from node v π(i) to node v π(i+1) . This will imply that the length of the exploration scheme E G ,s is at least

7 2 n + odd(m) -2 + 2(d -2) ( 3
)
where d is the number of edges in tour τ which are not in G.

Consider an index i (2 ≤ i ≤ n -1) such that (v π(i) , v π(i+1) ) is not an edge in G. If q i = 0, that is, if Agent-1 does not explore any bridge node between the explorations of nodes v π(i) and v π(i+1) , then it needs at least 4 steps to move from node v π(i) to node v π(i+1) because the distance between these two nodes is 4.

If q i > 0, then let b 1 , b 2 , . . . , b q i be the bridge nodes explored by Agent-1 between the explorations of nodes v π(i) and v π(i+1) . Agent-1 visits node v π(i) (for the first time), then it goes to a meeting point z (which cannot be b 1 ), and then to node b 1 . This takes at least 3 steps, because the distance between node v π(i) and node z is at least 2 (if z is not a bridge node) or the distance between node z and node b 1 is at least 2 (if z is a bridge node). Similarly, Agent-1 needs at least 3 steps to move from node b q i to node v π(i+1) . To move from node b j to node b j+1 , for j = 1, . . . , q i -1, Agent-1 needs at least 2 steps. Thus Agent-1 needs at least 3 + 2(q i -1) + 3 = 2q i + 4 steps to reach node v π(i+1) from the first visit to node v π(i) . The bound given by (3) on the length of the exploration scheme E G ,s implies that

cost(E G ,s ) ≥ 7 2 n + 2d -6. This implies that if cost(E G ,s ) ≤ 7 2 n + 1 (1 + ε), then d ≤ 7 4 εn + ε 2 + 7 2 , INRIA and cost(τ ) = n + d ≤ n + 7 4 εn + ε 2 + 7 2 = n(1 + ε 0 ) -(ε 0 - 7 4 ε)n + ε 2 + 7 2 < n(1 + ε 0 ), provided that 7 4 ε < ε 0 and n ≥ n 0 = ( ε 2 + 7
2 )/(ε 0 -7 4 ε) .

A 6-approximation algorithm for the General BHS Problem

Let G = (V, E) be the network to be explored, with the sets S and U defined as in Section 2. Let u = |U |. We define the distance graph G as the complete weighted graph in which the set of nodes corresponds to the nodes in U ∪ {s} and the weight of edge (v i , v j ) is the shortest path distance from v i to v j in G (considering both safe and unexplored nodes). An example of G is presented in Figure 2. Note that weights in G satisfy triangle inequality.

Let T be a minimum spanning tree of G rooted at s, and let cost(T ) be its cost, i.e., the sum of the weights of all its edges. Let L T = z 0 = s, z 1 , . . . , z 2u = s be an Euler tour of T . Let L G = w 0 = s, w 1 , w 2 , . . . , w q = s be the sequence obtained from L T by inserting between each pair of consecutive nodes z i and z i+1 , for i = 0, 1, . . . , z 2u-1 , the inner nodes of a shortest path in G between z i and z i+1 . The length of L G is twice the cost of T . We now construct the exploration scheme E G,S,s = (X, Y) for G based on the walk L G . Initially X = Y = s . Then, for i = 1, 2, . . . , q, the currently last node in X and Y is w i-1 , we consider node w i in L G , and extend the sequences X and Y in the following way. If node w i is in S or has already occurred in L G before, then append w i to both X and Y. Otherwise, append w i , w i-1 , w i to X and w i-1 , w i-1 , w i to Y. That is, if w i is a new unexplored node, then Agent-1 visits w i and goes back to node w i-1 , while Agent-2 waits for Agent-1 in node w i-1 . We call such two steps probing. The length of E G,S,s is equal to 2cost(T ) + 2u.

Lemma 16. The exploration scheme E G,S,s is feasible and can be constructed in polynomial time. Moreover, cost(E G,S,s ) ≤ 2cost(T ) + 2u.

Proof. Constraints 1 and 2 can be easily checked by observing that sequence L G (from which X and Y are derived) is a concatenation of paths in G, starting from s. All the nodes in U are in G, in L T and thus in L G ; moreover the insertion of probing phases does not alter the set of visited nodes, hence the agents visit all the unexplored nodes (Constraint 3). Observe that the agents always move together along explored nodes except for probing. Thus in each phase Agent-1 visits exactly one unexplored node, while Agent-2 does not visit any unexplored node. This implies that Constraint 4 is also satisfied. If B = ∅, then the agents spend 2u steps on probing and 2cost(T ) steps on following the Euler tour L T . If there is a black hole somewhere in the network, then the agents spend at most 2u steps on probing, and when Agent-2 finds out where the black hole is, it can return to node s by skipping some parts of the Euler tour L T . Thus the execution time in this case is at most 2cost(T ) + 2u. Hence the cost of the exploration scheme E G,S,s is 2cost(T ) + 2u.

! ! " # # # # $ $ % % $ & " & " & # & $ & % & $ & # & % '( )( ! & " & $ & # & % *( ! & " & # & $ & % +( ! " # $%& '%(%)%* '%*%$"%$( $%# "%) &%! ( $' +%$$ $&
Graph G can be constructed by computing all-pairs shortest paths in G; by using the best known algorithm [START_REF] Seidel | On the all-pairs-shortest-path problem in unweighted undirected graphs[END_REF], this operation has cost O(n ω log n), where O(n ω ) is the cost of a matrix product computation. This is the dominating cost of the whole algorithm, since the computation of the spanning tree T of G, as the computation of L T and L G can be all performed in linear time.

Let us consider now an optimal exploration scheme E * G,S,s = (X * , Y * ). In computing cost(E * G,S,s ) we consider, as a lower bound, the execution time of E * G,S,s in the case B = ∅. Let L = x k , . . . , s be the shortest path in G from the last node x k in X * to the starting node, excluding the endpoints x k and s.

Let L = X * • L • Y * • L • s .
L * = s • P (s, u 1 • P (u 1 , u 2 • . . . • P (u u , s
where u 1 , . . . , u u is the sequence of unexplored nodes in the order they are visited for the first time in L * , and P (x, y denotes the shortest path from node x (excluded) to node y in G. Since weights in G satisfy triangle inequality, the length of L * is equal to the length of the minimum traveling salesman tour in G, which is, by a well known relation, at least the cost of the minimum spanning tree T of G. Therefore, |L * | ≥ cost(T ), and

cost(E * G,S,s ) ≥ cost(T ) 2 . (4)
Moreover, since the agents cannot explore more than two nodes every two steps, the trivial lower bound still holds:

cost(E * G,S,s ) ≥ u. (5)
We compute the approximation ratio of the algorithm presented in this section, by choosing a suitable balance for Equations ( 4) and [START_REF] Dobrev | Mobile search for a black hole in an anonymous ring[END_REF]. Therefore:

cost(E G,S,s ) cost(E * G,S,s ) ≤ 2 cost(T ) + 2u 2 3 cost(T ) 2 + 1 3 u = 6 . (6)
Theorem 3. The BHS problem is approximable within 6.

We now show that the analysis of our approximation algorithm for the BHS problem is tight, i.e., the algorithm does not have a better approximation ratio than 6. Consider the instance (G, S, s) in Figure 3. Node s is the starting node and the gray nodes are the other safe nodes. There are u = 2k + 1 unexplored nodes: k pairs of unexplored nodes a i and b i , and node r. The edges are as indicated in the figure. A good exploration scheme for the network in Figure 3 would first explore node r, and then would explore pairs a i , b i , i = 1, 2, ..., by a-splits. The cost of such a scheme would be u + O(1).

Our approximation algorithm may compute the minimum spanning tree of G (rooted at s) in Figure 4. The edges adjacent to s have weight 1 while the other edges have weight 2.

For the exploration scheme computed by the approximation algorithm on the basis of this tree, the execution time for the case when node r is the black hole is 6u + O(1). The exploration of the sa 1 branch takes 2u + O(1) steps (4 steps to explore a new node), then going back to s takes u + O(1) steps, then the exploration of the s -b1 branch takes 2u + O(1) steps, and finally, going back to s after discovering that r is the black hole takes u + O(1) steps.

Conclusions

We showed that it is NP-hard to approximate within any factor less than 389 388 the problem of computing the fastest exploration scheme for the BHS with two agents (the BHS problem). We have also shown that for the restricted version of this problem (the rBHS problem), when initially only the starting node is known to be safe, approximating within any factor less than 2259 2258 is NP-hard. We have presented a polynomial-time 6-approximation algorithm for the BHS problem (while a polynomial-time 3 1 2 -approximation algorithm for the rBHS problem was previously shown in [START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF]).

It seems difficult to reduce significantly the gap between the upper and lower bounds on the approximation ratios for the BHS problem and the rBHS problem. Since our lower bounds are based on reductions from TSP(1,8) and TSP(1,2), any improvements of the inapproximability results for those problems will directly lead to improved lower bounds for our problems.

We have shown that the analysis of our approximation algorithm for the BHS problem is tight, i.e., the algorithm does not have a better approximation ratio than 6. However, we believe that one can find an approximation algorithm for the BHS problem with an approximation ratio better than 6. This might be achievable by considering the following two cases separately. If an MST T is such that cost(T )/(2u) is not close to 1, say it is outside the range [1δ, 1 + δ] for some small constant δ, then it can be shown that the ratio of costs given on the left-hand side of ( 6) is less than 6δ. If cost(T )/(2u) is within this range, then, using a similar analysis as in [START_REF] Klasing | Hardness and approximation results for black hole search in arbitrary graphs[END_REF], one might try to show that there is some other tree which gives a better bound for the ratio of costs in (6) than 6. This approach would however lead most likely only to a small improvement, while requiring substantial expansion and refinement of technical details.

As already observed in Section 1, it would be interesting to investigate how one could model and analyze the more practical and more general case of multiple black holes search, possibly performed by more than two agents. It is interesting to observe that the assumption of having at most one black hole in the network does not make the algorithm presented in Section 5 unsuitable for the general case. A (single black hole) search can be restarted for each new black hole found, on the network obtained by removing all the black holes already found and by inserting into S the nodes already explored. This can be iterated until all the network nodes become explored. Obviously, even if at most two agents simultaneously coexist in the network, the total number of agents needed is still related to the total number of black holes in the network.

Constraint 4 :

 4 for each phase with a sequence of steps j + 1, j + 2, . . . , k , (a) | {x j+1 , . . . , x k } \ S j | ≤ 1 and | {y j+1 , . . . , y k } \ S j | ≤ 1; and (b) {x j+1 , . . . , x k } \ S j = {y j+1 , . . . , y k } \ S j .

Fig. 1 .

 1 Fig. 1. An example of the reduction from an instance (G, d) of TSP(1,M) (in a)) to an instance (G , S, s) of BHS problem (in b)). The nodes in S are filled with gray color.

1 .

 1 While there are two unexplored nodes b , b adjacent to s: b-split(s, b , b ). 2. For each i = 2, . . . , n: INRIA (a) walk(b ), where b is either the bridge node b π(i-1),π(i) , if nodes v π(i-1) and v π(i)are adjacent in G, or any bridge node adjacent to I π(i) otherwise. (b) a-split(b , v π(i) , v π(i) , b ), where b is either the bridge node b π(i),π(i+1) , if i < n and nodes v π(i) and v π(i+1) are adjacent in G, or any bridge node adjacent to I π(i) otherwise.

Fig. 2 .

 2 Fig. 2. a) An instance (G, S, s) of the BHS problem. The gray nodes are the nodes in S.b) The corresponding distance graph G. c) The ordering in the Euler tour L T of the nodes of G (the numbers in italic). d) The L G sequence of the nodes of G. Note that some nodes of G may not be in L G while some may occur more than once.

INRIA

  The sequence L starts from s, visits all the nodes in U and ends in s. The length of L (we denote it as |L |) is at most twice the execution time of E * G,S,s in the case B = ∅, since L is the concatenation of the paths the two agents follow during the exploration in such case; hence 2cost(E * G,S,s ) ≥ |L |. Let L * be the minimum (shortest) tour in G starting from s and visiting all the nodes in U , and let |L * | be its length; obviously, |L | ≥ |L * |. Due to its optimality, L * has the following structure:

2 Fig. 3 .

 23 Fig. 3. The instance (G, S, s).

2 Fig. 4 .

 24 Fig. 4. A possible minimum spanning tree of G (rooted at s).

-approximation algorithm. In[START_REF] Czyzowicz | Searching for a black hole in tree networks[END_REF] the problem is studied in tree topologies, and the main results are an exact linear-time algorithm for some sub-class of trees and a 5/3-approximation algorithm for arbitrary trees. The existence of an exact polynomial-time algorithm for arbitrary trees is left open.

RR n°6185

In the following we will use the terms graph and network, host and node, and link and edge interchangeably, although we tend to use the term graph to mean an abstract representation of a network.INRIA

Research supported in part by the European Research Training Network COMBSTRU HPRN-CT-2002-00278 and the European COST Action TIST 293 (GRAAL), the Royal Society Grant ESEP 16244, and the ACI Masses de données. Part of this work was done while E.


Ahmad El

Rola Kiwan
email: kiwan@lmpt.univ-tours.fr

EXTREMAL FIRST DIRICHLET EIGENVALUE OF DOUBLY CONNECTED PLANE DOMAINS AND DIHEDRAL SYMMETRY

Keywords: 2000 Mathematics Subject Classification. 35J10, 35P15, 49R50, 58J50 eigenvalues, Dirichlet Laplacian, Schrödinger operator, extremal eigenvalue, obstacle, dihedral group

We deal with the following eigenvalue optimization problem: Given a bounded domain D ⊂ R 2 , how to place an obstacle B of fixed shape within D so as to maximize or minimize the fundamental eigenvalue λ 1 of the Dirichlet Laplacian on D \ B. This means that we want to extremize the function ρ → λ 1 (D \ ρ(B)), where ρ runs over the set of rigid motions such that ρ(B) ⊂ D. We answer this problem in the case where both D and B are invariant under the action of a dihedral group Dn, n ≥ 2, and where the distance from the origin to the boundary is monotonous as a function of the argument between two axes of symmetry. The extremal configurations correspond to the cases where the axes of symmetry of B coincide with those of D.

Introduction and Statement of the main Result

The relations between the shape of a domain and the eigenvalues of its Dirichlet or Neumann Laplacian, have been intensively investigated since the 1920's when Faber [START_REF] Faber | dass unter allen homogenen membranen von gleicher fläche und gleicher spannung die kreisförmige den tiefsten grundton gibt[END_REF] and Krahn [START_REF] Krahn | Über eine von Rayleigh formulierte Minimaleigenschaft des Kreises[END_REF] have proved independently the famous eigenvalue isoperimetric inequality first conjectured by Rayleigh (1877): the first Dirichlet eigenvalue λ 1 (Ω) of any bounded domain Ω ⊂ R n satisfies

λ 1 (Ω) ≥ λ 1 (Ω * ),
where Ω * is a ball having the same volume as Ω. We refer to the review papers of Ashbaugh [START_REF] Ashbaugh | Open problems on eigenvalues of the Laplacian[END_REF][START_REF] Ashbaugh | Isoperimetric and universal inequalities for eigenvalues[END_REF] and Henrot [START_REF] Henrot | Minimization problems for eigenvalues of the Laplacian[END_REF] for a survey of recent results on optimization problems involving eigenvalues.

The present work deals with the following eigenvalue optimization problem: Given a bounded domain D, we want to place an obstacle (or a hole) B, of fixed shape, inside D so as to maximize or minimize the fundamental eigenvalue λ 1 of the Laplacian or Schrödinger operator on D \ B with Zero Dirichlet conditions on the boundary.

In other words, the problem is to optimize the principal eigenvalue function ρ → λ 1 (D \ ρ(B)), where ρ runs over the set of rigid motions such that ρ(B) ⊂ D.

The first result obtained in this direction concerned the case where both D and B are disks of given radii. Indeed, it follows from Hersch's work [START_REF] Hersch | The method of interior parallels applied to polygonal or multiply connected membranes[END_REF] that the maximum of λ 1 is achieved when the disks are concentric (see also [START_REF] Ramm | Inequalities for the minimal eigenvalue of the Laplacian in an annulus[END_REF]). This result has been extended to any dimension by several authors (Harrell, Kröger and Kurata [START_REF] Harrell | On the placement of an obstacle or a well so as to optimize the fundamental eigenvalue[END_REF], Kesavan [START_REF] Kesavan | On two functionals connected to the Laplacian in a class of doubly connected domains[END_REF], ...). Actually, Harrell, Kröger and Kurata [START_REF] Harrell | On the placement of an obstacle or a well so as to optimize the fundamental eigenvalue[END_REF] gave a more general result showing that, if the domain D satisfies an interior symmetry property with respect to a hyperplane P passing through the center of the spherical obstacle B (which means that the image by the reflection with respect to P of one component of D \ P is contained in D), then the Dirichlet fundamental eigenvalue λ 1 (D \ B) decreases when the center of B moves perpendicularly to P in the direction of the boundary of D. In the particular case where both the domain D and the obstacle B are balls, this implies that the minimum of λ 1 (D \ B) corresponds to the limit case where B touches the boundary of D.

Notice that when the obstacle B is a disk, only translations of B may affect the λ 1 of D \ B and the optimal placement problem reduces to the choice of the center of B inside D.

In the present work we investigate a kind of dual problem in the sense that we consider a nonspherical obstacle B whose center of mass is fixed inside D, and seek the optimal positions while turning B around its center.

It is of course hopeless to expect a universal solution to this problem. In fact, we will restrict our investigation to a class of domains satisfying a dihedral symmetry and a monotonicity conditions.

Thus, let D be a simply-connected plane domain and assume that the following conditions are satisfied:

(i) (D n -symmetry) for an integer n ≥ 2, D is invariant under the action of the dihedral group D n of order 2n generated by the rotation ρ 2π n of angle 2π n and a reflection S. Such a domain admits n axes of symmetry passing through the origin and such that the angle between 2 consecutive axes is π n . (ii) (monotonicity of the boundary) the distance d(O, x) from the origin to a point x of the boundary of D is monotonous as a function of the argument of x, in a sector delimited by two consecutive symmetry axes.

Notice that assumption (i) guarantees that the center of mass of D is at the origin. Regular n-gones centered at the origin are the simplest examples of domains satisfying these assumptions. More generally, if g is any positive even 2π n -periodic continuous function that is monotonous on the interval (0, π n ), then the domain

D = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < g(θ)},
satisfies assumptions (i) and (ii). Actually, up to a rigid motion, any domain satisfying assumptions (i) and (ii) can be parametrized in such a manner. It is worth noticing that, due to the monotonicity condition, the "distance to the origin" function on the boundary of D achieves its maximum and its minimum alternatively at the intersection points of ∂D with the 2n half-axes of symmetry. The n points of ∂D at maximal (resp. minimal) distance from the origin will be called "outer vertices" (resp. "inner vertices") of D.

Our main result is the following Theorem 1. Let D and B be two plane domains satisfying the assumptions of D n -symmetry and monotonicity (i) and (ii) above for an integer n ≥ 2. Assume furthermore that B has C 2 boundary and that ρ(B) ⊂ D for all ρ ∈ SO(2). Then, the fundamental Dirichlet eigenvalue λ 1 (D \ B) of D \ B is optimized exactly when the axes of symmetry of B coincide with those of D.

The maximizing configuration corresponds to the case where the outer vertices of B and D lie on the same half-axes of symmetry (we will then say that B occupies the "ON" position in D).

The minimizing configuration corresponds to the case where the outer vertices of B lie on the half-axes of symmetry passing through the inner vertices of D (this is what will be called the "OFF" position).

Actually, we will prove that, except for the trivial case where D or B is a disk, the fundamental Dirichlet eigenvalue of D \ B decreases gradually when B switches from "ON" to "OFF".

The main ingredients of the proof of Theorem 1 are Hadamard's variation formula for λ 1 and the technique of domain reflection initiated by Serrin [START_REF] Serrin | A symmetry problem in potential theory[END_REF] in PDE's setting.

Examples of maximal (left) and minimal (right) configurations

with n = 2, 3 and 4 respectively

Extensions of Theorem 1 to the following situations can be obtained up to slight changes in the proof (indeed, only the Hadamard formula should be replaced by the variation formula corresponding to the new functional):

(1) Soft obstacles: instead considering the Dirichlet Laplacian on D \ B, we consider the Schrödinger type operator

H(α, B) := ∆ -αχ B
acting on H 1 0 (D), where α > 0 and χ B is the indicator function of B. Optimization problems related to the fundamental eigenvalue of operators of this kind have been investigated in particular in [START_REF] Harrell | On the placement of an obstacle or a well so as to optimize the fundamental eigenvalue[END_REF] and [START_REF] Chanillo | Symmetry breaking and other phenomena in the optimization of eigenvalues for composite membranes[END_REF]. Under the assumptions of Theorem 1 on D and B, ∀α > 0, the fundamental eigenvalue of H(α, B) achieves its maximum at the "ON" position and its minimum at the "OFF" position.

(2) Wells: this case corresponds to the operator H(α, B) with α < 0. Under the circumstances of Theorem 1, ∀α < 0, the first eigenvalue of H(α, B) achieves its maximum at the "OFF" position and its minimum at the "ON" position.

(3) Stationary problem : the problem now is to optimize the Dirichlet energy

J(D \ B) := D\B |∇u| 2 dx of the unique solution u of the problem ∆u = -1 in D \ B u = 0 on ∂(D \ B),
This problem was treated in [START_REF] Kesavan | On two functionals connected to the Laplacian in a class of doubly connected domains[END_REF]Section 2] in the case where both D and B are balls. Under the assumptions of Theorem 1 on D and B, one can prove that J(D \ B) achieves its maximum when B is at the "ON" position and its minimum when B is at the "OFF" position.

Proof of the main result

Without loss of generality, we may assume that the domain D and the obstacle B are centered at the origin and are both symmetric with respect to the x 1 -axis so that they can be parametrized in polar coordinates by

D = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < g(θ)}, B = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < f (θ)},
where f and g are two positive even 2π n -periodic functions which are nondecreasing on (0, π n ). To avoid technicalities, we suppose throughout that g is continuous and f is C 2 . Extensions of our result to a wider class of domains would certainly be possible up to some additional technical difficulties.

The condition that the obstacle B can freely rotate around his center inside D, that is ρ( B) ⊂ D for all ρ ∈ SO(2), amounts to the following:

f ( π n ) = max 0≤θ≤2π f (θ) < min 0≤θ≤2π g(θ) = g(0).
Let us denote, for all t ∈ R, by ρ t the rotation of angle t, that is,

∀ζ ∈ R 2 ∼ = C, ρ t (ζ) = e it ζ,
and set

B t := ρ t (B) and Ω(t) := D \ B t .
Let λ(t) be the fundamental eigenvalue of the Dirichlet Laplacian on Ω(t). It is well known that, since it is simple, the first Dirichlet eigenvalue λ(t) is a differentiable function of t (see [START_REF] Garabedian | Convexity of domain functionals[END_REF][START_REF] Rellich | New results in the perturbation theory of eigenvalue problems, in Simultaneous linear equations and the determination of eigenvalues[END_REF] ). We denote by u(t) the one parameter family of nonnegative first eigenfunctions satisfying, ∀t ∈ R,

   ∆u(t) = -λ(t)u(t) in Ω(t) u(t) = 0 on ∂Ω(t) Ω(t) u 2 (t) = 1.
The derivative of λ(t) is then given by the following so-called Hadamard formula (see [START_REF] El Soufi | Domain deformations and eigenvalues of the Dirichlet Laplacian in a Riemannian manifold[END_REF][START_REF] Garabedian | Convexity of domain functionals[END_REF][START_REF] Hadamard | Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées[END_REF][START_REF] Schiffer | Hadamard's formula and variation of domain-functions[END_REF]):

(1)

λ ′ (t) = ∂Bt ∂u(t) ∂η t 2 η t • v dσ,
where η t is the inward unit normal vector field of ∂Ω(t) (hence, along ∂B t the vector η t is outward with respect to B t ) and v denotes the restriction to ∂Ω(t) = ∂D ∪ ∂B t of the deformation vector field. In our case, the vector v vanishes on ∂D and is given by v(ζ) = iζ for all ζ ∈ ∂B t . Since both Ω and B are invariant by the dihedral group D n , it follows that, ∀t ∈ R, Ω(t + 2π n ) = Ω t . Moreover, if we denote by S 0 the reflection with respect to the x 1 -axis, then we clearly have ρ -t = S 0 • ρ t • S 0 which gives B -t = S 0 (B t ) and Ω -t = S 0 (Ω t ). Hence, as a function of t, the first Dirichlet eigenvalue of Ω t is even and periodic of period 2π n , that is, ∀t ∈ R, λ(t + 2π n ) = λ(t) and λ(-t) = λ(t). Therefore, it suffices to investigate the variations of λ(t) on the interval 0, π n and Theorem 1 is a consequence of the following:

Theorem 2. Assume that neither D nor B is a disk. (i) ∀t ∈ 0, π n , λ ′ (t) < 0. Hence, λ(t) is strictly decreasing on 0, π n . (ii) ∀k ∈ Z, λ ′ (k π n ) = 0 and k π n , k ∈ Z,
are the only critical points of λ on R. Hence, λ(t) achieves its maximum for t = 0 mod 2π n which corresponds to the "ON" position, and its minimum for t = π n mod 2π n which corresponds to the "OFF" position. Of course, if D or B is a disk, then the function λ(t) is constant.

In what follows we will denote, for any α ∈ R, by z α the θ = α axis, that is z α := {re iα ; r ∈ R}, and by z + α the half-axis {re iα ; r ≥ 0}. We start the proof with the following elementary lemma. Lemma 1. Let K be a plane domain defined in polar coordinates by K = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < h(θ)}, where h is a positive 2π-periodic function of classe C 1 , and let v be a vector field whose restriction to ∂K is given by v(θ) := v(h(θ)e iθ ) = ih(θ)e iθ = h(θ)e i(θ+ π 2 ) .

We denote by η the unit outward normal vector field of ∂K. One has, at any point h(θ)e iθ of ∂K where η is defined,

(i) η(θ) := η(h(θ)e iθ ) = h(θ)e iθ -ih ′ (θ)e iθ √ h 2 (θ)+h ′2 (θ) (ii) η • v(θ) = -h(θ)h ′ (θ) √ h 2 (θ)+h ′2 (θ)
. Hence, η.v(θ) has constant sign on an interval I if and only if h is monotonous in I. (iii) if for some α > 0, the domain K is symmetric with respect to the axis z α , then the function η • v is antisymmetric w.r.t this axis, that is

η • v(α + θ) = -η • v(α -θ).
Proof. Assertions (i) and (ii) are direct consequences from the definition of K. The fact that K is symmetric with respect to the axis z α implies that the function h satisfies h(α + θ) = h(αθ). Therefore, (iii) follows immediately from (ii).

We will denote by S α the symmetry with respect to the axis z α . We will also denote, for α < β, by σ (α, β) the sector delimited by z + α and z + β , that is σ (α, β) = {re iθ ; r > 0 and α < θ < β}. Lemma 2. Let D be as above. For all t ∈ 0, π n , we have:

S π n +t D ∩ σ π n + t, 2π n + t ⊆ D ∩ σ t, π n + t .
Moreover, if D is not a disk, then

S π n +t ∂D ∩ σ π n + t, 2π n + t ∩ D = ∅.
Proof. The action of the symmetry S π n +t is given in polar coordinates by S π n +t (re iθ ) = re i(2( π n +t)-θ) . Hence,

S π n +t D ∩ σ π n + t, 2π n + t = S π n +t (D) ∩ σ t, π n + t .
Moreover, the domain D being parametrized by a positive even 2π n -periodic function g(θ), that is D = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < g(θ)}, its image S π n +t (D) can be parametrized in the same manner by the function g * (θ) = g(θ -2t). Thus

S π n +t (D) ∩ σ t, π n + t = {re iθ ; θ ∈ t, π n + t , 0 ≤ r < g(θ -2t)}.
Therefore, we need to prove that F (θ) = g(θ)g * (θ) is nonnegative for every θ in the interval (t, π n + t). This will be possible thanks to the assumptions of symmetry (that is g is even and 2π n -periodic) and monotonicity (that is g is nondecreasing on [0, π n ]). Indeed, these properties imply that on the interval t, π n + t , • g achieves its maximum at θ = π n , • g * achieves its minimum at θ = 2t. Four cases must be considered separately: -If t < θ ≤ min{2t, π n }, we may write, since g is even, F (θ) = g(θ)-g(2t-θ), with 0 ≤ 2t-θ < θ ≤ π n . Since g is nondecreasing on [0, π n ], we get F (θ) ≥ 0. -If max{2t, π n } ≤ θ < π n + t, we may write, since g is even and 2π n -periodic,

θ = 0 t θ = θ = 2 t θ = π \ n θ = π \ n + t θ = 2 π \n θ = 2π \n +t θ = 0 t θ = θ = π \ n θ = π \ n + t θ = 2
F (θ) = g(2 π n -θ)-g(θ-2t) with 0 ≤ θ-2t < 2 π n -θ ≤ π n . Hence, F (θ) ≥ 0.
-If 2t < π n and 2t ≤ θ ≤ π n , then 0 ≤ θ -2t < θ ≤ π n and, then,

F (θ) = g(θ) -g(θ -2t) ≥ 0. -If 2t > π n and π n ≤ θ ≤ 2t, then 0 ≤ 2t -θ < 2 π n -θ ≤ π n and, then, F (θ) = g(2 π
nθ)g(2tθ) ≥ 0. Hence, F (θ) is nonnegative for all θ in (t, π n + t). Now, if D is not a disk, then g is nonconstant on [0, π n ]. Following the arguments above, we deduce that the function F (θ) is positive somewhere on (t, π n + t) which means that S π n +t ∂D ∩ σ π n + t, 2π n + t meets the interior of D. Proof of Theorem 2. Notice first that, since λ is an even and 2π n -periodic function of t, one immediately gets, ∀k ∈ Z, λ(k π nt) = λ(k π n + t) and, then,

λ ′ k π n = 0.
Alternatively, one can deduce that λ ′ k π n = 0 from Hadamard's variation formula (1) after noticing that the domain Ω(k π n ) is symmetric with respect to the x 1 -axis and that the first Dirichlet eigenfunction u(k π n ) satisfies u • S 0 = u, where S 0 is the symmetry with respect to the x 1 -axis.

Let us fix a t in 0, π n and denote by u the nonnegative first Dirichlet eigenfunction of Ω(t) satisfying Ω(t) u 2 = 1. The domain Ω(t) is clearly invariant by the rotation ρ 2π n of angle 2π n , hence u • ρ 2π n = u. On the other hand, the domain B being parametrized by a positive even 2π n -periodic function f (θ), that is

B = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < f (θ)}, one has B t = {re iθ ; θ ∈ [0, 2π), 0 ≤ r < h(θ)}, with h(θ) = f (θ -t). Hence, the function η t • v is invariant by ρ 2π
n (Lemma 1) and we have (Hadamard formula (1))

λ ′ (t) = ∂Bt ∂u ∂η t 2 η t • v dσ = n ∂Bt∩σ(t, 2π n +t) ∂u ∂η t 2 η t • v dσ.
Since B t is symmetric with respect to the axis z π n +t , we have (Lemma 1), Hence, the function w(x) = u(x)u(x * ) is well defined on H(t) and satisfies w(x) = 0 for all x in ∂H(t) ∩ ∂B t ∪ z π n +t ∪ z 2π n +t . Moreover, since u vanishes on ∂D and is positive inside Ω(t), w(x) ≤ 0 for all x in ∂H(t) ∩ ∂D and w(x) < 0 for certain x in ∂H(t) ∩ ∂D (recall that D is not a disk and apply the second part of Lemma 2). Therefore, the nonconstant function w satisfies the following: ∆w = -λ(t)w in H(t) w ≤ 0 on ∂H(t).

η t • v( π n + t + θ) = -η t • v( π n + t -θ) or, equivalently, η t • v(x) = -η t • v(x * ),
Hence, w must be nonpositive on the whole of H(t). Otherwise, a nodal domain V ⊂ H(t) of w would have the same first Dirichlet eigenvalue as Ω(t). But, due to the invariance of Ω(t) by ρ 2π n , the domain Ω(t) would contain n copies of V leading to a strong contradiction with the domain monotonicity theorem for eigenvalues. Therefore, ∆w ≥ 0 in H(t) and w achieves its maximal value (i.e. zero) on ∂B t ∩ σ(

  where x * denotes the symmetric of x with respect to z π n +t . This yields

	λ ′ (t) = n	∂Bt∩σ( π n +t, 2π n +t)	∂u ∂η t	(x)	2	-	∂u ∂η t	(x * )	2	η t • v(x) dσ
	Notice that the function h(θ) is decreasing between π n + t and 2π n + t and, then, η t • v is nonnegative on ∂B t ∩ σ( π n + t, 2π n + t) (Lemma 1). Let H(t) := Ω(t)∩σ( π n +t, 2π n +t). Applying Lemma 2, and since B t is symmetric with respect to the axis z π n +t , one gets
		S π n +t (H(t)) ⊂ Ω(t) ∩ σ(t,	π n	+ t).

  π n + t, 2π n + t) ⊂ ∂H(t). The Hopf maximum principle (see [13, Theorem 7, ch.2]) then implies that, at any regular point x of ∂B t ∩ σ( π n + t, 2π n + t), one has It follows that λ ′ (t) ≤ 0 and that the equality holds if and only if η t • v ≡ 0. By Lemma 1, this last equality occurs if and only if f is constant which means that B is a disk.

	∂w ∂η t	(x) =	∂u ∂η t	(x) -	∂u ∂η t	(x * ) < 0.