Lali Barrière

Paola Flocchini

Fedor V Fomin

Pierre Fraigniaud

Nicolas Nisse

Nicola Santoro

Dimitrios M Thilikos

V Fomin

Connected Graph Searching

Keywords: Graph searching, cops-and-robbers, network security

published or not. The documents may come   L'archive ouverte pluridisciplinaire

Results of this paper have appeared in the proceedings of the 14th ACM Symposium on Parallel Algorithm and Architecture (SPAA 2002), the 29th Workshop on Graph Theoretic Concepts in Computer Science (WG 2003), the 13th SIAM Conference on Discrete Mathematics, (DM 2006), and the 7th Latin American Theoretical Informatics Symposium (LATIN 2006).

2 Paola Flocchini and Nicola Santoro are supported in part by NSERC Discovery Grant; Pierre Fraigniaud is supported by the ANR projects ALADDIN and PROSE, and by the INRIA project GANG; Nicolas Nisse is supported by the ANR project AGAPE; Dimitrios M. Thilikos is supported by the project "Kapodistrias" (AΠ 02839/28.07.2008) of the National and Kapodistrian University of Athens (project code: 70/4/8757).

Introduction

The classical isoperimetric problem (often attributed to Dido, the legendary founder and first queen of Carthage) can be stated as follows: Among all closed curves in the plane of given length, which curve encloses the maximum region? While the circle appears to be an intuitive solution to the problem, it took several thousands of years to develop tools for proving this apparently evident fact. There is a conceptual link between the isoperimteric problem and the principle of least action in physics. The most familiar illustration of this link is the shape of a water drop: given a fixed amount of water, the surface tension forces the drop to take a shape which minimizes the surface area of the drop. The study of discrete versions of the isoperimetric problem in graphs has brought to the notion of expander graphs, a notion that is now extensively used in different areas of mathematics and computer science [START_REF] Hoory | Expander graphs and their applications[END_REF].

A natural extension of discrete isoperimetric problem is the following dynamic version, where the task is to expand a subset of elements S into another set T via a sequence of steps, under the constraint that, at every step, the surface area -or simply its border size -be as small as possible. Let us give two illustrative examples of frameworks in which this constrained expansion process finds application. The first example is from visualization, specifically from the domain of compression techniques design used for streaming triangular meshes over communication channels with limited bandwidth. 3D meshes are used for a variety of applications in entertainment, e-commerce, CAD, and medicine. Quite often, those meshes are acquired using modern 3D scanning technologies, and they easily reach sizes of gigabytes. A common approach for processing large meshes (those that are too large to fit into main memory) is to perform a "conquest" of the mesh by starting from an arbitrary triangle, and by successively extending the frontier by conquering a new vertex adjacent to one of the current conquered triangles. A lower bound on the memory requirements for processing a streaming mesh is then provided by the number of "border" vertices bounding the conquered part of the mesh [START_REF] Gotsman | On the optimality of valence-based connectivity coding[END_REF][START_REF] Isenburg | Large mesh simplification using processing sequences[END_REF].

The second example is from agent-based software-system testing [START_REF] Jennings | An agent-based approach for building complex software systems, Commun[END_REF]. Given a set of interrelated functional units in a distributed system, the objective is to check the correctness of these units, one by one. In order to avoid checked units to be subject to propagation of faults from neighboring unchecked units, the "checker" uses resources to protect checked units against unchecked neighboring ones. Once all neighboring units of a checked unit U have been checked, there is no need to protect U anymore, and only the frontier between checked and unchecked units has to be guarded. The objective is to minimize the amount of resources required for the system to be entirely checked.

Both illustrative problems can be modelled as graph searching. In a graph searching game, alternatively known as a pursuit-evasion game, the one part is a set of "escaping" mobile entities, called fugitives (or evaders), that hide in a graph representing a network, and the other part is a number of "chasing" entities, called searchers (or pursuers), that move systematically in the graph and aim at capturing the evaders [START_REF] Megiddo | The complexity of searching a graph[END_REF]. The game may vary significantly according to the capabilities of the fugitives and the searchers in terms of relative speed, sensor capabilities, visibility, mobility restrictions, etc. [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF]. These variants are mainly application driven. However, their study has inspired, and was linked to foundational issues in computer science. Some of the former and current applications of graph searching are VLSI design [START_REF] Möhring | Graph problems related to gate matrix layout and PLA folding[END_REF], computational complexity [START_REF] Kirousis | Searching and pebbling[END_REF], network security [START_REF] Franklin | Eavesdropping games: a graph-theoretic approach to privacy in distributed systems[END_REF], and databases [START_REF] Gottlob | Generalized hypertree decompositions: NPhardness and tractable variants[END_REF].

The first mathematical models for the analysis of graph searching games where introduced in the 70's by Parsons [START_REF] Parsons | Pursuit-evasion in a graph[END_REF][START_REF] Parsons | The search number of a connected graph[END_REF] and Petrov [START_REF] Petrov | A problem of pursuit in the absence of information on the pursued[END_REF], while the first variants, along with the corresponding algorithmic and complexity results, appeared during the 80's [START_REF] Kirousis | Interval graphs and searching[END_REF][START_REF] Kirousis | Searching and pebbling[END_REF][START_REF] Megiddo | The complexity of searching a graph[END_REF]. Graph searching revealed the need to express several intuitive informal concepts in a formal mathematical way. These concepts include sense of direction/orientation, avoidance, surrounding, hiding, persecution, threatening, etc. This led to the design of various advanced combinatorial tools. Some of most powerful tools for tackling graph searching problems emerged from the Graph Minors theory, developed by Robertson and Seymour towards proving the long-standing Wagner's Conjecture [START_REF] Robertson | Graph minors. XX. Wagner's conjecture[END_REF]. This theory has offered deep graph-theoretic results and techniques with direct consequences to problems at the core of graph searching games.

In many applications of graph searching, especially those aiming at clearing a network, a crucial issue is to guarantee secure communication channels between the searchers so that they can safely exchange information. In graph-theoretic terms, the clean part of the network is required to remain always connected. Unfortunately, the aforementioned combinatorial and algorithmic tools used for tackling the graph searching problem, i.e., those tools coming from Graph Minors theory, generally fail under such a global connectivity restriction. Hereafter, we provide two open problems whose solutions currently escape the reach of Graph Minors theory. Let us define a search strategy as an ordered sequence S of actions where each action is either placing a searcher at a vertex, or removing a searcher from a vertex, or sliding a searcher along an edge. The invisible fugitive is supposed to move arbitrarily fast from node to node along the edges of the graph, and it can traverse any node that is not occupied by a searcher.

NP-membership.

A straightforward reduction from classical graph searching shows that the problem of checking whether a graph G can be connectedly cleared using at most k searchers is NP-hard. However, NP-membership remains an insisting open problem. The standard approach for proving NP-membership for searching problems is to prove that the corresponding game is monotone, i.e. strategies allowing the fugitive to revisit (or "recontaminate") an already cleaned part of the graph cannot do better than strategies for which recontamination is not allowed. See, e.g., [START_REF] Bienstock | Monotonicity in graph searching[END_REF][START_REF] Lapaugh | Recontamination does not help to search a graph[END_REF]. If a game is monotone then NP-membership follows directly from the fact that the existence of a monotone search strategy yields the existence of a search strategy with a bound on its length, and such a strategy can be used as a succinct certificate. A basic technique for proving monotonicity (emerging from the Graph Minors theory) is to represent each search strategy as an expansion of clean edges, i.e., as a sequence E of edge sets X 0 , X 1 , . . . , X t (representing the clean territories at search step i) where X 0 = ∅, X t = E, and |X i+1 \X i | ≤ 1 for every i = 0, 1, . . . , t-1. The objective is to find an expansion that minimizes the maximum frontier size of the X i 's, where the frontier of a set X ⊆ E, is defined as the set of vertices ∂(X) that are both incident to an edge in X and to an edge in E \X. Let us denote by δ(X) the number of vertices in ∂(X). It has been observed in [START_REF] Bienstock | Monotonicity in graph searching[END_REF][START_REF] Fomin | On the monotonicity of games generated by symmetric submodular functions[END_REF] that monotonicity essentially follows from the fact that δ is a submodular function, that is, for every

X, Y ⊆ E, δ(X ∩ Y ) + δ(X ∪ Y ) ≤ δ(X) + δ(Y ).
However, the submodularity does not have a counterpart for connected search games because X ∩ Y is not necessarily connected. As first observed in [START_REF] Yang | Sweeping graphs with large clique number[END_REF], connected search is not monotone, which implies than the conjectured NP-membership of the connected variant requires techniques beyond monotonicity to be proved.

Polynomial time algorithms for fixed parameter. Monotonicity also establishes a close relationship between graph searching and various notions of width, including pathwidth for graph searching, and treewidth for "visible" graph searching. In particular, it enables the design of efficient exponential-time exact or polynomial-time approximation algorithms for computing the minimum number of searchers required to clear a graph (see, e.g., [START_REF] Bodlaender | Approximating treewidth, pathwidth, frontsize, and shortest elimination tree[END_REF][START_REF] Fomin | Nondeterministic graph searching: from pathwidth to treewidth[END_REF]). For almost all width parameters related to graphs searching, the problem is polynomial-time solvable for fixed parameter [START_REF] Bodlaender | Computing small search numbers in linear time[END_REF]. In contrast, the absence of monotonicity in the case of connected graph searching precludes using these powerful tools in this context. More specifically, let us denote by s(G) the minimum number of searchers required to search (i.e., to clean) the graph G, and by cs(G) the analogous graph searching parameter in the case where only connected strategies are permitted. Let us first explain why the problem of checking whether a given graph G satisfies s(G) ≤ k can be solved in polynomial time for every fixed non-negative integer k. The main observation is that the class

G k = {G | s(G) ≤ k} is minor-closed. That is, if H is a minor of G ∈ G k (i.e.,
C k = {G | cs(G) ≤ k}
is not minor-closed. Actually, it is possible to show that parameter cs can increase twice by removing just a single edge. Therefore it seems that the design of an algorithm that checks cs(G) ≤ k in polynomial time for fixed k requires tools beyond those provided by the yet powerful Graph Minors theory.

Our results

The results in this paper are directly motivated by the above open questions, and they constitute a first attempt to studying the impact of the connectivity requirement on graph searching problems. This impact is measured by the ratio cs(G) s(G) between the number cs(G) of searchers required to clear a graph G under the connectivity constraint, and the number s(G) of searchers required to clear the same graph in absence of such a constraint. In other words, this paper tackles the price of connectivity in graph searching. In this paper we make advances in understanding the price of connectivity by proving the following two results:

1. For each connected n-vertex graph G, cs(G) s(G) = O(log n); 2. For each tree T , cs(T) s(T) < 2.
To derive the first of these two results, we use the concept of a branch-decomposition introduced by Robertson and Seymour in [START_REF] Robertson | Graph minors. X. Obstructions to tree-decomposition[END_REF]. Branch-decompositions provide ways to decompose a graph into smaller parts that are arranged in a tree-like fashion. Our result is based on the fact that these parts can be made connected while maintaining the "separation cost" of this decomposition (cf. Lemma 1). Then, by suitably defining an "orientation" of this connected branch-decomposition, we are able to transform every search strategy into a connected one, with just a logarithmic overhead on its cost in term of number of involved searchers. These results, combined with existing recently derived algorithmic results on approximating the size of minimal separators, and on approximating the value of the treewidth, imply that cs(G) can be approximated in polynomial time up to a multiplicative factor O(log 3/2 n).

Our second result is derived from a complete characterization of the connected search number of trees. We first prove that, as opposed to the case of arbitrary graphs, connected search is monotone on trees (cf. Lemma 3). Next, we identify, for each k, the obstruction set for the class T k = {T | cs(T ) ≤ k}. That is, we identify the set of contraction-minimal trees that are not in T k . We stress that this identification provides one of the very few examples of contraction-closed graph classes for which the obstruction set can be entirely characterized. In fact, somewhat surprisingly, the obstruction set for T k is reduced to one element, which is in contrast to the fact that the size of the obstruction set of all classic (non-connected) graph searching parameters is growing (at least) exponentialy as a function of k. These combinatorial results are used for the design of a linear-time algorithm computing cs(T ) for trees. This algorithm makes use of the rooted variant, cs v (T ), of the connected search number, in which we prescribe the vertex v of T from which the connected search strategy should expand. An important byproduct of the design of our algorithm for trees is that cs v (T ) is equal to -and thus may serve as an alternative definition for -the Horton-Strahler number [START_REF] Horton | Erosional development of streams and their drainage basins: hydrophysical approach to quantitative morphology[END_REF][START_REF] Strahler | Hypsometric (area-altitude) analysis of erosional topology[END_REF][START_REF] Strahler | Quantitative analysis of watershed geomorphology[END_REF]. This latter ubiquitous number serves as a measure of the "branching complexity" of a rooted tree, and is known to find applications in many different areas of science for the statistical analysis of hierarchical systems (including hydrology [START_REF] Gleyzer | A fast recursive GIS algorithm for computing Strahler stream order in braided and nonbraided networks[END_REF], programming languages [START_REF] Flajolet | The number of registers required for evaluating arithmetic expressions[END_REF], mathematical biology [START_REF] Borchert | Bifurcation ratios and the adaptive geometry of trees[END_REF][START_REF] Horsfield | Some mathematical properties of branching trees with application to the respiratory system[END_REF] and, recently, social networks [START_REF] Arenas | Community analysis in social networks[END_REF]).

All the results summarized above, in conjunction with additional considerations to be detailed further in the text, allow us to conjecture the following:

lim n→∞ sup |V (G)|=n cs(G) s(G) = 2. ( 1
)
In other words, we conjecture that what we have proved for trees actually holds for all graphs. The validity of this conjecture would imply -and there are indications for this (cf. Section 3)that the tree structure is critical towards evaluating the price of connectivity. Conceptually, graph searching parameters ask for a "sense of direction" in a graph, or, stated differently, for an arrangement of the vertices along a virtual axis along which the optimal search strategy should be deployed. Informally, the connectivity requirement places another constraint on the direction to be followed by the searchers during the deployment of the search strategy. As indicated in the proof of Theorem 2, the existence of these two possibly conflicting directions is the key motivation for our conjecture. In some sense, there are empirical evidences that the worst-case conflict between these two orientations occurs in trees.

Related work

Graph searching is a well studied model in Mathematics and Theoretical Computer Science. The first mathematical formulation of graph searching is due to Parsons [START_REF] Parsons | Pursuit-evasion in a graph[END_REF][START_REF] Parsons | The search number of a connected graph[END_REF]. The formulation was inspired by an earlier article of Breisch in Southwestern Cavers Journal [START_REF] Breisch | An intuitive approach to speleotopology[END_REF] proposing a "speleotopological" approach for the problem of finding an explorer lost in a system of dark caves. Megiddo et al. [START_REF] Megiddo | The complexity of searching a graph[END_REF], proved that the decision version of the problem is NP-complete in general and solvable in linear time on trees. Let us remark that the proof that the problem is in NP is based on the highly non-trivial fact that there are optimal monotone strategies [START_REF] Bienstock | Monotonicity in graph searching[END_REF][START_REF] Lapaugh | Recontamination does not help to search a graph[END_REF]. For more references on graph searching, we refer to [START_REF] Fomin | An annotated bibliography on guaranteed graph searching[END_REF].

Since the appearance of the conference versions of this paper in [START_REF] Barrière | Capture of an intruder by mobile agents[END_REF][START_REF] Barrière | Searching is not jumping[END_REF], the connected graph searching has been studied both from algorithmic and combinatorial points of view. Yang et al. proved that for the connected variant of searching, recontamination can be useful [START_REF] Yang | Sweeping graphs with large clique number[END_REF]. The "cost of connectivity": the ratio between the number of searchers required in the connected case and the number of searchers required without the connectivity requirement, was studied in [START_REF] Fomin | Connected graph searching in outerplanar graphs[END_REF][START_REF] Fraigniaud | Connected treewidth and connected graph searching[END_REF][START_REF] Nisse | Connected graph searching in chordal graphs[END_REF].

A related problem on planar triangulations was studied in [START_REF] Nowakowski | Boundary-optimal triangulation flooding[END_REF]. Connected searching with visible fugitive is discussed in [START_REF] Fraigniaud | Monotony properties of connected visible graph searching[END_REF]. Finally, distributed connected search strategies have been designed in [START_REF] Blin | Distributed chasing of network intruders[END_REF][START_REF] Flocchini | Decontamination of chordal rings and tori using mobile agents[END_REF][START_REF] Flocchini | Decontamination of hypercubes by mobile agents[END_REF][START_REF] Ilcinkas | The cost of monotonicity in distributed graph searching[END_REF][START_REF] Nisse | Graph searching with advice[END_REF].

Model and definitions

Graph searching refers to a problem that has been thoroughly and extensively investigated in the literature, and that describes a variety of application scenarios ranging from "decontaminating a set of tunnels" to "capturing an intruder in a network".

Using the original metaphor [START_REF] Breisch | An intuitive approach to speleotopology[END_REF][START_REF] Parsons | Pursuit-evasion in a graph[END_REF], we are given a graph whose edges are all "contaminated", and a set of "searchers". The goal is to obtain a state of the graph in which all edges are simultaneously "clear". To clear an edge e = (u, v), a searcher must traverse the edge from one end-point u to the other end-point v. A clear edge is preserved from recontamination if either another searcher remains in u, or all other edges incident to u are clear. In other words, a clear edge e is recontaminated if there exists a path between e and a contaminated edge, with no searcher on any node of the path. The basic operations, called search steps, can be the following:

(1) place a searcher on a node, (2) move a searcher along an edge,

(3) remove a searcher from a node.

Graph searching is the problem of developing a search strategy, that is a sequence of search steps that results in all edges being simultaneously clear. The main complexity measure is the number of searchers used by the strategy. The smallest number of searchers for which a search strategy exists for a graph G is called the search number s(G) of G.

An interesting line of investigation is the determination of efficient search strategies satisfying additional properties, which are desirable or even necessary for some applications. Two properties are of particular interest: absence of recontamination, and connectivity of the cleared area.

A search strategy is monotone if no recontamination ever occurs. The importance of monotone searching arises in applications where the cost of clearing an edge by far exceeds the cost of traversing an edge. Hence each edge should be cleared only once. Lapaugh [START_REF] Lapaugh | Recontamination does not help to search a graph[END_REF] has proved that for every G there is always a monotone search strategy that uses s(G) searchers. A short and elegant proof of this result was found by Bienstock and Seymour [START_REF] Bienstock | Graph searching, path-width, tree-width and related problems (a survey)[END_REF][START_REF] Bienstock | Monotonicity in graph searching[END_REF].

A search strategy is connected if the set of clear edges is always connected. Alternatively, one can define such strategies by not allowing operation (3), and allowing (1) only in the beginning of the search or when applied to vertices incident to an already cleared edge. The necessity for connectivity arises, e.g., in applications where communication between the searchers can occur only within completely clear areas of the network. Hence connectivity is required for their coordination. Moreover, the same condition should be imposed in cases where the searchers cannot "jump" from one node to a non-adjacent one (e.g., cannot pass through the "walls" that determine the structure of the graph where the search takes place). Safety is another motivation for connectivity, as it would always ensure the presence of secure routes between all the searchers. We denote by cs(G), the connected search number of graph G, the minimum number of searchers required to clear all edges of G by making use of connected strategy. Correspondingly, the monotone connected search number of graph G, mcs(G), is the minimum number of searchers required to clear all edges of G by making use of connected and monotone strategy.

Price of connectivity

The main result of this section is the following theorem.

Theorem 1. For any n-vertex graph G, cs(G)/s(G) = O(log n).
To prove the theorem, we introduce several auxiliary notions and statements.

Branchwidth. A branch decomposition [START_REF] Seymour | Call routing and the ratcatcher[END_REF] of a graph G = (V, E) is a tree T with all internal vertices of degree 3 and with a one-to-one correspondence between the leaves of T and the edges of G. Given an edge e of T , removing e from T results in two trees T

(e) i ⊂ E is the set of leaves of T (e) i for i = 1, 2. Note that E (e) 1 ∩ E (e) 2 = ∅ and E (e) 1 ∪ E (e) 2 = E. The width of T is defined as ω(T ) = max e δ(E (e) 1 )
where the maximum is taken over all e-cuts in T , see Figure 1. The branchwidth of G is then bw(G) = min T ω(T ), where the minimum is taken over all branch decompositions T of G. For the purpose of our proof, we define the following notion.

2. ∂(A 1 , B 1 ) = ∅ and ∂(A 2 , B 2 ) = ∅; 3. ∂(A 1 , A 2 ) = ∅;
Let us notice that by the above definition, the leaves corresponding to the subtrees

A 1 , A 2 , B 1 , B 2 form a 4-partition of E.
In Figure 3, we provide Algorithm Make-it-Connected which proceeds as follows. Given a quartet (A 1 , A 2 , B 1 , B 2 ) in S, the algorithm replaces this quartet by (A 1 , B 1 , A 2 , B 2 ), resulting in a tree S obtained by connecting a 1 and b 1 to x, and a 2 and b 2 to y (See Fig. 2). Actually, if (A 1 , A 2 , B 1 , B 2 ) and (A 1 , A 2 , B 2 , B 1 ) are both quartets in S, then the algorithm considers the two possible replacements, and chooses the one that has smaller width. Clearly S is also a branch decomposition of G. Note however that neither

(A 1 , B 1 , A 2 , B 2 ), nor (A 2 , B 2 , A 1 , B 1 ) is a quartet in S since ∂(A i , B i ) = ∅ for i = 1, 2, by the definition of the quartet (A 1 , A 2 , B 1 , B 2 ) in S.
Algorithm Make-it-Connected proceeds by successive replacements of quartets in the branch decomposition. The algorithm stops when there is no quartet in the current branchdecomposition (we later prove that such a situation eventually occurs).

The next Lemma is the most crucial part in the proof of Theorem 1.

2. ∂(A 1 , B 1 ) = ∅ and ∂(A 2 , B 2 ) = ∅; 3. ∂(A 1 , A 2 ) = ∅;
Let us notice that by the above definition, the leaves corresponding to the subtrees

A 1 , A 2 , B 1 , B 2 form a 4-partition of E.
In Figure 3, we provide Algorithm Make-it-Connected which proceeds as follows. Given a quartet (A 1 , A 2 , B 1 , B 2 ) in S, the algorithm replaces this quartet by (A 1 , B 1 , A 2 , B 2 ), resulting in a tree S obtained by connecting a 1 and b 1 to x, and a 2 and b 2 to y (See Fig. 2).

Actually, if (A 1 , A 2 , B 1 , B 2 ) and (A 1 , A 2 , B 2 , B 1 ) are both quartets in S, then the algorithm considers the two possible replacements, and chooses the one that has smaller width. Clearly S is also a branch decomposition of G. Note however that neither (

A 1 , B 1 , A 2 , B 2 ), nor (A 2 , B 2 , A 1 , B 1 ) is a quartet in S since ∂(A i , B i ) = ∅ for i = 1, 2, by the definition of the quartet (A 1 , A 2 , B 1 , B 2 ) in S.
Algorithm Make-it-Connected proceeds by successive replacements of quartets in the branch decomposition. The algorithm stops when there is no quartet in the current branch-decomposition (we later prove that such a situation eventually occurs).

Let us notice that by the above definition, the leaves corresponding to the subtrees A 1 , A 2 , B 1 , B 2 form a 4-partition of E.

In Figure 3, we provide Algorithm Make-it-Connected which proceeds as follows. Given a quartet (A 1 , A 2 , B 1 , B 2 ) in S, the algorithm replaces this quartet by (A 1 , B 1 , A 2 , B 2 ), resulting in a tree S obtained by connecting a 1 and b 1 to x, and a 2 and b 2 to y (See Fig. 2). Actually, if (A 1 , A 2 , B 1 , B 2 ) and (A 1 , A 2 , B 2 , B 1 ) are both quartets in S, then the algorithm considers the two possible replacements, and chooses the one that has smaller width. Clearly S is also a branch decomposition of G. Note however that neither (

A 1 , B 1 , A 2 , B 2 ), nor (A 2 , B 2 , A 1 , B 1 ) is a quartet in S since ∂(A i , B i ) = ∅ for i = 1, 2, by the definition of the quartet (A 1 , A 2 , B 1 , B 2 ) in S.
Algorithm Make-it-Connected proceeds by successive replacements of quartets in the branch decomposition. The algorithm stops when there is no quartet in the current branchdecomposition (we later prove that such a situation eventually occurs). Proof. The proof of the lemma proceeds through a sequence of claims.

a 2 x b 1 y b 2 a 1 A 1 B 1 b 1 x a 2 y b 2 a 1 A 1 B 1 B 2 A 2 A 2 B 2
Claim 1. The replacement of a quartet as specified in Algorithm Make-it-Connected does not increase the width of the branch-decomposition.

Proof. The only possible change in the width can occur because of the cut separating A 1 ∪A 2 from B 1 ∪ B 2 . We consider two cases depending whether or not (A

1 , A 2 , B 2 , B 1 ) is a quartet. If (A 1 , A 2 , B 2 , B 1 ) is also a quartet (i.e., ∂(A 1 , B 2 ) = ∅ and ∂(A 2 , B 1 ) = ∅), then δ(A 1 ∪ B 1 , A 2 ∪ B 2 ) + δ(A 1 ∪ B 2 , A 2 ∪ B 1 ) ≤ δ(E(B 1 )) + δ(E(B 2 )).
(2)

Indeed, if u ∈ ∂(A 1 ∪ B 1 , A 2 ∪ B 2 ) \ ∂(E(B 1 )) then u ∈ ∂(E(B 2 )) because ∂(A 1 , A 2 ) = ∅. Similarly, if u ∈ ∂(A 1 ∪ B 2 , A 2 ∪ B 1 ) \ ∂(E(B 2 )), then u ∈ ∂(E(B 1 )
). Therefore, every vertex counted on the left hand side of Equation 2 appears as many times on the right hand side. Thus Equation 2 holds. Hence

δ(A 1 ∪ B 1 , A 2 ∪ B 2 ) + δ(A 1 ∪ B 2 , A 2 ∪ B 1 ) ≤ 2k,
) = ∅. We get δ(A 1 ∪ B 1 , A 2 ∪ B 2 ) ≤ δ(E(B 1 )) ≤ k.
Claim 2. The branch decomposition T returned by Algorithm Make-it-Connected is connected.

input: branch decomposition T of a 2-edge-connected graph of width k; output: connected branch decomposition T of width ≤ k; begin S := T ;

while there exists a quartet (A Proof. Targeting towards a contradiction, let us assume that there is an e-cut that splits T into two subtrees A and B such that the edges of E(A) form a disconnected subgraph of G. Then there exists an e-cut such that A is the union of two disjoint subtrees A 1 and A 2 with ∂(A 1 , A 2 ) = ∅. Among all such cuts, we choose an e-cut with the maximum number |E(A)|. The other subtree B of this e-cut contains at least two leaves because otherwise removing the single edge corresponding to the leaf of B would result in disconnecting the graph G, a contradiction with the fact that G is 2-edge-connected. Thus B is the union of two disjoint subtrees B 1 and B 2 which roots are adjacent to the root of B. Since |E(A)| is maximum, we have that ∂(A, B i ) = ∅ for i = 1, 2. Moreover, since G is connected, and

1 , A 2 , B 1 , B 2 ) in S do replace (A 1 , A 2 , B 1 , B 2 ) in S by (A 1 , B 1 , A 2 , B 2 ) to get S ; if (A 1 , A 2 , B 2 , B 1 ) is not a quartet in S then S := S else replace (A 1 , A 2 , B 1 , B 2 ) in S by (A 1 , B 2 , A 2 , B 1 ) to get S ; if ω(S ) ≤ ω(S )
∂(A 1 , A 2 ) = ∅, we have ∂(A i , B) = ∅ for i = 1, 2. Therefore, either ∂(A 1 , B 1 ) = ∅ and ∂(A 2 , B 2 ) = ∅, or ∂(A 1 , B 2 ) = ∅ and ∂(A 2 , B 1 ) = ∅, or both.
In each of the cases, there is a quartet in T , which is a contradiction because the tree returned by Algorithm Make-it-Connected has no quartet.

Claim 3. Algorithm Make-it-Connected terminates.

Proof. We use a potential argument, based on a measure defined in [START_REF] Seymour | Call routing and the ratcatcher[END_REF] for carvings. Any internal vertex x of the branch-decomposition S is of degree 3, and thus it defines three subtrees S 1 , S 2 , S 3 whose roots are connected to x. Then let

φ(S 1 , S 2 , S 3 ) = 0, if ∂(S i , S j ) = ∅ for any i = j; |E(S )| -1, if ∂(S i , S j ) = ∅ for some i = j, where / ∈ {i, j}.
This function is well defined: G is connected and thus, if ∂(S i , S j ) = ∅ for some i = j, then ∂(S i , S ) = ∅ and ∂(S j , S ) = ∅ for ∈ {1, 2, 3} \ {i, j}. Now, we define a potential function φ defined on any branch-decomposition S with set of internal vertices I(S) by

φ(S) = x∈I(S) φ(S x 1 , S x 2 , S x 3 ).
We show that after every step of Algorithm Make-it-Connected φ strictly decreases. For that purpose, it is sufficient to prove that

φ(A 1 ∪ B 1 , A 2 , B 2 ) + φ(A 1 , B 1 , A 2 ∪ B 2 ) < φ(A 1 , A 2 , B 1 ∪ B 2 ) + φ(A 1 ∪ A 2 , B 1 , B 2 )
for every quartet (A 1 , A 2 , B 1 , B 2 ). By the definition of a quartet, ∂(A 1 , A 2 ) = ∅, and we get that

φ(A 1 , A 2 , B 1 ∪ B 2 ) = |E(B 1 )| + |E(B 2 )| -1. Hence, for L = φ(A 1 ∪B 1 , A 2 , B 2 )+φ(A 1 , B 1 , A 2 ∪B 2 ) and R = φ(A 1 ∪A 2 , B 1 , B 2 )+|E(B 1 )|+|E(B 2 )|-1,
it is enough to prove that L < R for every quartet (A 1 , A 2 , B 1 , B 2 ). Since R > 0, the lemma holds if L = 0. Thus we restrict our analysis to the case L > 0, which means that either

φ(A 1 ∪ B 1 , A 2 , B 2 ) > 0 or φ(A 1 , B 1 , A 2 ∪ B 2 ) > 0. W.l.o.g.
we can examine the case where

φ(A 1 , B 1 , A 2 ∪ B 2 ) > 0 which excludes that ∂(A 1 , A 2 ∪ B 2 ) = ∅ and ∂(B 1 , A 2 ∪ B 2 ) = ∅ hold simultaneously.
Hence we consider two cases:

Case 1: ∂(A 1 , A 2 ∪ B 2 ) = ∅. If ∂(A 1 ∪ B 1 , A 2 ) = ∅ and ∂(A 1 ∪ B 1 , B 2 ) = ∅ then L = |E(B 1 )| -1 < |E(B 1 )| + |E(B 2 )| -1 ≤ R.
Therefore, we consider two sub-cases:

• If ∂(A 1 ∪B 1 , A 2 ) = ∅, then L = |E(B 1 )|+|E(B 2 )|-2 < |E(B 1 )|+|E(B 2 )|-1 ≤ R. • If ∂(A 1 ∪ B 1 , B 2 ) = ∅, then ∂(B 1 , B 2 ) = ∅, and thus R = |E(A 1 )| + |E(A 2 )| + |E(B 1 )| + |E(B 2 )| -2. It follows that L < R because, by the definition of a quartet, ∂(A i , B i ) = ∅ for every i = 1, 2. Case 2: ∂(B 1 , A 2 ∪ B 2 ) = ∅. Then ∂(B 1 , B 2 ) = ∅, and thus R = |E(A 1 )| + |E(A 2 )| + |E(B 1 )| + |E(B 2 )| -2. Hence, L < R because ∂(A i , B i ) = ∅ for every i = 1, 2.
In all cases, the inequality L < R holds, which completes the proof. Now everything is settled to conclude with the proof of the lemma. By Claims 1 and 2, if Algorithm Make-it-Connected terminates, then it returns a connected branch decomposition of width ≤ k. By Claim 3, the algorithm terminates. To compute the execution time of the algorithm, let us consider the potential function φ defined in the proof of Claim 3. Since φ(S 1 , S 2 , S 3 ) ≤ m -1, we have that the potential cannot exceed O(m 2 ). Thus there are O(m 2 ) updates of the branch-decomposition. Each update is local to the subtree of six vertices interconnecting the roots

a 1 , a 2 , b 1 , b 2 of A 1 , A 2 , B 1 , B 2 .
For each of the edges {x, a 1 }, {x, b 1 }, {y, a 2 }, {y, b 2 }, deciding whether the edge defines a quartet takes O(m) times. Thus Algorithm Make-it-Connected terminates in O(m 3 ) steps.

Expansions is a convenient tool for addressing the graph searching problem.

Connected Expansions. Let G = (V, E) be a graph (with possible multiple edges and loops), and let n = |V |, and m = |E|. A k-expansion in G is a sequence X 0 , X 1 , . . . , X r where X i ⊆ E for every i = 0, . . . , r, X 0 = ∅, X r = E, and satisfying the following:

• |X i+1 \ X i | ≤ 1 for every i = 0, . . . , r -1;
• δ(X i ) ≤ k for every i = 0, . . . , r.

A k-expansion X 0 , X 1 , . . . , X r is monotone, if X i+1 ⊂ X i for every i = 0, . . . , r -1. Using the terminology of [START_REF] Bienstock | Monotonicity in graph searching[END_REF], a k-expansion is hence a crusade of frontier at most k. In this paper we deal only with expansions in graphs, however this notion can be defined for more general structures as well [START_REF] Fomin | On the monotonicity of games generated by symmetric submodular functions[END_REF].

A k-expansion X 0 , X 1 , . . . , X r of a graph G is connected if for each i = 1, . . . , r, the subgraph formed by edges X i is connected.

Proof. We prove by induction on the number m of edges in G a slightly stronger statement: Given a connected branch decomposition T of width k for a graph G, and given any edge e of G, one can compute in O(m 3 )-time a monotone connected (k log 2 m)-expansion X 0 , X 1 , . . . , X m in G with X 1 = {e}.

For any m ≥ 1, let P m be the following property: for any k ≥ 0, given a connected branch decomposition T of width k for a graph G with m edges, and given any edge e of G, one can compute in O(m 3 )-time a monotone connected (k log 2 m)-expansion X 0 , X 1 , . . . , X m in G with X 1 = {e}. We now show that P m is satisfied.

If m = 1, then ∅ = X 0 , X 1 , where X 1 is the only edge of G, is the connected 0-expansion in G, and thus P 1 holds. If m = 2, then G is either a path of three vertices, or two vertices linked by an edge and a loop attached to one of the two vertices, or two loops attached to a vertex, or two vertices connected by a double edge. In the first three cases, bw(G) = 1. In the latter case bw(G) = 2. In all cases though, one can construct a connected bw(G)-expansion X 0 , X 1 , X 2 in G starting from any edge. Thus P 2 holds.

For m > 2, let us assume that P q holds for every 2 ≤ q ≤ m -1. There is a vertex x of T whose removal results in three disjoint subtrees T 1 , T 2 , and T 3 , with |E i | ≤ m/2 for every i ∈ {1, 2, 3}, where |E i | is the number of leaves of T i . Since T is a connected branch decomposition, we have that the leaves of each of these subtrees form three connected subgraphs G 1 , G 2 , G 3 of G, and, for any i ∈ {1, 2, 3}, T i is a connected branch decomposition of G i . Given a set of edges X in G i = (V i , E i ), we denote by ∂ G i (X) the set of vertices of G i that has at least one incident edge in X, and at least one incident edge in E i \ X.

Because m > 2 and m/2 < m -1, we have that each G i (with m i ≤ m/2 edges) satisfies the induction assumption. Let e be an edge of G. Edge e belongs to some G i . Assume, w.l.o.g., that e is an edge of G 1 . By the induction assumption, there is a monotone connected (k log 2 m 1 )-expansion X 0 , X 1 , . . . , X m 1 in G 1 with X 1 = {e}. Removing the edge connecting x to the root of T 3 in T results in a connected subgraph G 1 ∪ G 2 . Thus, there is a vertex u in G that has at least one incident edge in G 1 , and at least one incident edge f in G 2 . Again, by the induction assumption, there is a (k log

2 m 2 )-expansion Y 0 , Y 1 , . . . , Y m 2 in G 2 with Y 1 = {f }. Finally, since G is connected and G = G 1 ∪ G 2 ∪ G 3 ,
we have that there is a vertex v in G that has at least one incident edge in G 1 ∪ G 2 , and at least one incident edge g in G 3 . By the induction assumption, we can select a monotone connected (k log 2 m 3 )-expansion Z 0 , Z 1 , . . . , Z m 3 in G 3 with Z 1 = {g}. By putting three expansions together, we obtain a monotone connected expansion

X 0 , X 1 , . . . , X m 1 , X m 1 ∪ Y 1 , . . . , X m 1 ∪ Y m 2 , X m 1 ∪ Y m 2 ∪ Z 1 , . . . , X m 1 ∪ Y m 2 ∪ Z m 3
in G. It remains to bound the "frontier" of this expansion. We have

δ(X i ) ≤ δ G 1 (X i ) + k ≤ k log 2 m 1 + k ≤ k log 2 m/2 + k ≤ k log 2 m/2 + k ≤ k log 2 m.
We also have

δ(X m 1 ∪ Y i ) ≤ δ G 2 (Y i ) + δ(X m 1 ∪ Y i , G 3 ) ≤ k log 2 m/2 + k ≤ k log 2 m.
Finally, we have

δ(X m 1 ∪ Y m 2 ∪ Z i ) ≤ δ G 3 (Z i ) + δ(Z i , G 1 ∪ G 2 ) ≤ k log 2 m/2 + k ≤ k log 2 m.
Hence P m is satisfied.

To complete the proof of the lemma, we observe that the time τ (m) needed to construct the expansion in an m-edge graph satisfies τ (m) ≤ 3τ (m/2), and thus the complexity of the construction is 3 log 2 m = O(m 3 ). Now everything is ready to proceed with the proof of the main result of this section.

Proof of Theorem 1. If bw(G) ≤ 1, then G is isomorphic to K 1,p , the tree with at most one non-leaf vertex. In this case, cs(G) = s(G).

cs(G) = s(G) =      0, if p = 0; 1, if p ≤ 2; 2, if p > 2 Claim 4. Given a branch decomposition T of width k ≥ 2 for a connected graph G, one can compute in O(m 3 )-time a monotone connected k(1 + log 2 m)-expansion X 0 , X 1 , . . . , X m in G.
Proof. Indeed, if G is 2-edge-connected, then by application of Lemma 1, one can compute in O(m 3 ) time a connected branch decomposition T of G of width ≤ k. The requested expansion is then obtained by Lemma 2. If G is not 2-edge-connected, then we add a double edge to each isthmus (i.e., cut-edge) in G so that the resulting graph G is 2-edge-connected. Since k ≥ 2, we obtain that bw(G ) = bw(G). More precisely, given a branch decomposition T of G, one can construct a branch decomposition T of G such that ω(T ) = ω(T ). We construct G and T , and then compute a connected branch decomposition T of G in time O(m 3 ). We have ω(T ) ≤ ω(T ) ≤ ω(T ) = k. By application of Lemma 2, we obtain a monotone connected (k log m )-expansion in G . By removing in this expansion the second occurrence of every double edge added to isthmuses, we obtain a connected (k log 2 m )expansion in G. We complete the proof by noticing that m ≤ 2m.

Finally, by Claim 4, there is a monotone connected k(1 + log 2 m)-expansion X 0 , X 1 , . . . , X m in G. This expansion can be transformed into a monotone connected strategy of k(1+log 2 m)+1 searchers as follows. Suppose that for some i ≥ 1, k(1+log 2 m)+1 searchers are able to clean the set of edges X i and that the only vertices occupied by the searchers at this step are the vertices of ∂(X i ). Moreover, every vertex of ∂(X i ) contains exactly one searcher. For X 1 , which consists of one edge, 1 ≤ δ(X 1 ) ≤ 2, and this condition clearly holds. Let e = {x, y} = X i+1 \ X i . Expansion X 0 , X 1 , . . . , X m is connected and thus at least one of the endpoints of e, say x, is in ∂(X i ). Because δ(X i ) ≤ k(1 + log 2 m), there is at least one unused searcher. We put this searcher on x, clear e by sliding from x to y, and then remove searchers from all vertices of ∂(X i ) \ ∂(X i+1 ). We also remove one searcher from y if y ∈ ∂(X i ) ∩ ∂(X i+1 ), and thus arrive to the situation when all edges of X i+1 are cleared, and the searchers occupy the vertices of ∂(X i+1 ). By repeating these arguments for each 1 ≤ i ≤ m -1, we construct a monotone search strategy of at most k(1 + log 2 m) + 1 searchers. To conclude, for any graph G, bw(G) ≤ s(G) [START_REF] Bienstock | Monotonicity in graph searching[END_REF][START_REF] Robertson | Graph minors. X. Obstructions to tree-decomposition[END_REF]. Hence, we construct a monotone search strategy of at most s(G)(1 + log 2 m) + 1 searchers.

Let us remark, that the proof of Theorem 1 implies a more general result, namely, mcs(G)/s(G) = O(log n).

Connected search in trees

Price of connectivity in trees

In this section we show that the price of connectivity in trees is at most 2. In particular, we prove the following theorem.

Theorem 2. For any tree T that is not a line, it holds that s(T ) ≤ cs(T ) ≤ 2 • s(T ) -2 and this inequality is tight.

Our first step is the following lemma on the monotonicity of cs on trees. Lemma 3. For any tree T with connected search number at most k, there exists a monotone connected search strategy for T using at most k searchers. In other words, cs(T ) = mcs(T ) for any tree T .

Proof. Let T be a tree, with cs(T ) ≤ k. Let T be the tree obtained from T by subdividing every edge e of T into two consecutive edges e and e . Consider a connected search strategy for T , and replace every slide action along an edge e in this strategy by two consecutive slide actions along the corresponding edges e and e . That way we get a connected search strategy for T using the same number of searchers as the original strategy for T . As a consequence,

cs( T ) ≤ cs(T ).

Claim 5. There exists a connected k-expansion in T .

Proof. To prove the claim, let us consider a connected search strategy S in T using at most k searchers. Let F = X 0 , X 1 , . . . , X t be the sequence of subsets of edges defined as follows: X 0 = ∅, and, for i ≥ 1, X i is the set of clear edges after step i of S. Since at most one edge is cleared at every step of S, it follows that |X i \ X i-1 | ≤ 1, i.e., F is an expansion. As S is using at most k searchers, we obtain that the frontier of each set in F is of size at most k. Finally, all X i 's are connected for 1 ≤ i ≤ t because S is a connected strategy.

The core of the proof of the lemma is the following result: Claim 6. There exists a monotone connected k-expansion in T .

Proof. By Claim 5, there exists a connected k-expansion in T . Let us choose a connected k-expansion X 0 , X 1 , . . . , X t in T that satisfies:

(C1) t i=0 (δ(X i ) + 1) is minimum, and (C2) t i=0 |X i | is minimum subject to (C1). Let us show that X 0 , X 1 , . . . , X t is monotone. If for some i ≥ 1, |X i \ X i-1 | = 0, i.e., if X i ⊆ X i-1 , then X 0 , X 1 , . . . , X i-1 , X i+1 , . . . , X t is also a connected k-expansion, contradicting (C1). Therefore |X i \ X i-1 | = 1 for every i ≥ 1. Now, we show that X i-1 ⊆ X i for every i ≥ 1. First, observe that δ(X i-1 ∪ X i ) ≥ δ(X i ) (3)
for every i ≥ 1. Indeed, assume for the purpose of contradiction that δ(X

i-1 ∪ X i ) < δ(X i ). Then X i-1 ∪ X i is connected because otherwise δ(X i-1 ∪ X i ) = δ(X i-1 ) + δ(X i ) ≥ δ(X i ). Therefore, X 0 , X 1 , . . . , X i-1 , X i-1 ∪ X i , X i+1 , . . . , X r is a connected k-expansion because |(X i-1 ∪ X i ) \ X i-1 | = |X i \ X i-1 | ≤ 1 and |X i+1 \ (X i-1 ∪ X i )| ≤ |X i+1 \ X i | ≤ 1.
This connected k-expansion would yield a contradiction with (C1), and Equation 3 follows. To prove X i-1 ⊆ X i for every i ≥ 1, we use the submodularity of the connectivity function δ, stating that for any two edge-sets A and B of any graph,

δ(A ∩ B) + δ(A ∪ B) ≤ δ(A) + δ(B)
. By combining submodularity with Equation 3, we get that δ(X i-1 ∩ X i ) ≤ δ(X i-1 ) for every i ≥ 1. Therefore

X 0 , X 1 , . . . , X i-2 , X i-1 ∩ X i , X i , . . . , X t is a k-expansion because |(X i-1 ∩ X i ) \ X i-2 | ≤ |X i-1 \ X i-2 | ≤ 1 and |X i \ (X i-1 ∩ X i )| = |X i \ X i-1 | ≤ 1.
The fact that this expansion is connected follows from the fact that both X i-1 and X i are subtrees of T , and therefore their intersection is also a subtree of T , and thus connected.

By (C2), |X i-1 ∩ X i | ≥ |X i-1 |
, and thus X i-1 ⊆ X i . Therefore, the considered expansion is a monotone connected k-expansion, which completes the proof.

Claim 7. There exists a monotone connected search strategy in T using at most k searchers.

Proof. Let X 0 , X 1 , . . . , X t be a monotone connected k-expansion in T whose existence is guaranteed by Claim 6. For i = 1, . . . , t, let

e i = {x i , y i } = X i \ X i-1 .
If one of the endpoints of e i is of degree 1, then x i is set to be that vertex. We construct a monotone connected search strategy that successively clears the edges e 1 , e 2 , . . . , e t , as follows. Initially, place k searchers in x 1 . Clear edge e 1 by sliding one searcher from x 1 to y 1 along e 1 . No recontamination occurs because either k = 1 and x 1 is incident to e 1 only, or k > 1 and k -1 searchers remains at x 1 . Assume now that all edges e 1 , . . . , e i-1 have been cleared (without recontamination).

The edge e i = {x i , y i } is incident to X i-1 because the expansion X 0 , X 1 , . . . , X t is connected. Assume, w.l.o.g., that x i ∈ ∂(X i-1 ). If δ(X i-1 ) < k, then there is at least one free searcher, which can be slid from x i to y i along e i to clear that edge without recontamination. If δ(X i-1 ) = k, then we claim that at least one endpoint of e i is not in ∂(X i ). Indeed, since

x i ∈ ∂(X i-1 ), if x i ∈ ∂(X i ) then deg(x i ) > 2.
As a consequence, y i has to be of degree exactly 2 because every edge has one of its endpoints incident to exactly one other edge. If in turn y i ∈ ∂(X i ) then the unique edge f i = e i incident to y i is contaminated, and therefore

y i / ∈ ∂(X i-1
). We get a contradiction because then δ(X i ) = δ(X i-1 ) + 1 > k, contradicting the fact that we are dealing with a k-expansion. So, as claimed, at least one endpoint of e i is not in ∂(X i ). If x i ∈ ∂(X i ) and y i / ∈ ∂(X i ) then, as shown before, deg(y i ) = 2, and the unique edge f i = e i incident to y i belongs to X i-1 . Therefore, there is at least one searcher occupying y i , which can be slid along e i to clear it without recontamination. If

x i / ∈ ∂(X i )
then this vertex is occupied by at least one searcher because x i ∈ ∂(X i-1 ). This searcher can be slid along e i from x i to y i , clearing e i without recontamination. One proceeds that way until all edges have been cleared. During the process, no recontamination occurs and the successive sets of clear edges are always connected. Hence, the constructed search strategy is monotone and connected. By construction, it uses at most k searchers.

To complete the proof of Lemma 3, we observe that we can directly get a monotone connected search strategy in T using at most k searchers from the monotone connected search strategy in T using at most k searchers by merely replacing the clearing of each edge in T by the clearing of the corresponding subdivided edge in T .

The proof of Theorem 2 is based on the notion of k-caterpillar recursively defined as follows:

• a 0-caterpillar is a path graph,

• for k ≥ 1, a graph G is a k-caterpillar if it is a tree containing a path P , called spine, such that, for any connected component C of G \ V (P ), C is a (k -1)
-caterpillar with an extremity of its spine adjacent to a vertex in P .

The spine of a 0-caterpillar is the graph itself. Notice that, according to the above definition, an 1-caterpillar is a subdivision of a caterpillar in the usual sense, i.e., a path x 1 , . . . , x k with k i ≥ 0 paths pending from every x i . Clearly, every tree is a k-caterpillar for k large enough. The notion of k-caterpillar is related to the notion of caterpillar dimension introduced in [START_REF] Matoušek | On embedding trees into uniformly convex Banach spaces[END_REF] (see also [START_REF] Linial | Trees and Euclidean metrics[END_REF]).

Our second step for the proof of Theorem 2 is to prove that k-caterpillars are exactly the graphs that can be connectedly cleared with at most k + 1 searchers.

Given a tree T and two vertices v, w of T , we denote by T v the tree T rooted at v, and by T v [w] the subtree of T v rooted at w. Recall that the depth of a rooted tree T is the maximum length of a path from its root to the leaves. We denote by B k the complete binary tree of depth k rooted on its unique vertex of degree 2, and by D k the tree obtained by connecting the three roots of three copies of B k-1 to a unique new root vertex. We denote by T 1 T 2 the relation "T 1 is a contraction of T 2 ". Finally, given a tree T 1 rooted on x 1 and a tree T 2 containing a vertex x 2 , we denote by T 1 x 2 T 2 the relation "T 1 is a x 2 -rooted minor of T 2 ", that is vertex x 1 is either x 2 or the result of contracting a series of edges, some of them containing x 2 as end-point.

Let T 1 , T 2 , and T 3 be the three sub-trees attached to the root of D k and isomorphic to B k-1 . Consider the first step i 1 during which an edge e incident to the root of D k is being cleaned. Assume, w.l.o.g., that e is an edge of T 1 , which means that after step i 1 , T 2 and T 3 are still completely contaminated. Let i 2 > i 1 be the first step during which an edge incident to a leaf f of T 2 or T 3 , say of T 2 is reached by a searcher. The path P from the root r to this leaf should be clean and has length k. Moreover, at step i 2 , for every vertex x = f of P , there is a path from x to a contaminated leaf, and thus at least one searcher is needed for every x for a monotone search. Moreover, there is one additional searcher used to clear f . Hence, at least k + 1 searchers are required at step i 2 .

Applying inductively Lemma 4 for the edges that are contracted in T in order to create D k , one can prove that mcs(T ) ≥ mcs(D k ). Therefore mcs(T ) ≥ k + 1 and the result follows from Lemma 3.

(3) ⇒ (1): We show the stronger statement that, if T is a k-caterpillar with spine P , then there is a connected search strategy using k +1 searchers starting at one extremity of P . The proof is by induction. For k = 0, a 0-caterpillar is a path and hence the result holds trivially. Assume now that every (k -1)-caterpillar with spine P = {w 0 , . . . , w } can be cleared with k searchers, starting at w 0 . Let T be a k-caterpillar with spine P = {v 0 , . . . , v m }. Let us denote by w i,0 . . . w i,d i the set of neighbors of v i not in P . Then, T w i,j [v i ] is a (k-1)-caterpillar with spine P i,j starting at w i,j . The search strategy for T is the following. Start at v 0 with k + 1 searchers. Every time you reach a new vertex v i of P , let one searcher at v i and, for j = 0, . . . , d i , clear every tree T w i,j [v i ] with the k remaining searchers, using the strategy that starts at w j (there is one, by induction hypothesis). Then, follow the path to the next contaminated vertex v i+1 , with the k + 1 searchers.

We define M k = {G | s(G) ≤ k} and D k = {G | cs(G) ≤ k} and denote by obs(M k ) (resp. obs(D k )) the set of all the contraction minimal graphs that do not belong in M k (resp. D k ). According to Lemma 5, obs(D k ) contains a unique graph that is D k . This comes to a contrast to the fact that the size of obs(M k ) increases rapidly as shown by Parsons in [START_REF] Parsons | The search number of a connected graph[END_REF] (in fact, |obs(M)| = 2 Ω(k log k) , as indicated in [START_REF] Takahashi | Minimal acyclic forbidden minors for the family of graphs with bounded path-width[END_REF]).

Proof of Theorem 2. Let T be a tree, and assume that s(T ) ≤ k. Let M k be any tree obtained from a complete ternary tree of depth k after removing one leaf from every set of three sibling leaves (i.e., vertices at distance k from the root). Parsons [START_REF] Parsons | The search number of a connected graph[END_REF] has proved that M k ∈ obs(M k ). Therefore M k T .

Observe that M k is a subgraph of the graph obtained from D 2k-2 by contracting every edge connecting a vertex of level 2j -1 to a vertex of level 2j, for 0 < j < k -1. Therefore,

for any k ≥ 1, M k D 2k-2 . Thus D 2k-2
T , which implies, by Lemma 5, that cs(T ) ≤ 2k -2 = 2s(T ) -2.

To prove that the bound is tight, we first consider D 2k-1 . We have s(D 2k-1 ) ≤ cs(D 2k-1 ) = 2k and M k D 2k-1 , which implies that s(D 2k-1 ) ≥ k + 1. On the other hand, we give a search strategy for D 2k-1 that uses k + 1 searchers. The strategy starts by placing a searcher in the root r. Next, it proceeds to clear the edges of the three branches which are isomorphic to B 2k-2 . It is easy to see that this can be done with k searchers, and the edges connecting r to the three branches need no additional searcher. Therefore cs(D 2k-1 ) = 2s(D 2k-1 ) -2.

Finally, let us consider the graph M k . It is easy to observe that D k+1

M k and that D k M k which, from Lemma 5, implies that cs(M k ) = k + 1 = s(M k ).

Computing optimal connected search strategies in trees

In this section, we show that computing the connected search number of trees can be achieved in polynomial time.

Theorem 3. There is a linear-time algorithm that, given any tree T , computes the connected search number and an optimal monotone connected search strategy for T .

The proof of Theorem 3 is constructive. A monotone connected strategy depends on the choice of the initial vertex x where all searchers are originaly placed. For every tree T , let cs x (T ) denote the minimum number of searchers required to clear T by a monotone connected strategy starting from vertex x. Hence, cs(T ) = min x∈V (T ) cs x (T ).

Our algorithm computes cs x (T ) for all vertices x of the tree T . In fact, it computes the related values cs + x (T ), x ∈ V (T ), where

cs + x (T ) = max{1, cs x (T )}.
The tree T rooted at vertex x is denoted by T x . For a vertex y of T , let T x [y] denote the subtree of T x rooted at y, consisting of y and all its descendants in T x . Our algorithm relies mostly on the following lemma: Lemma 6. Let y 1 , y 2 , . . . , y d be the d ≥ 1 children of vertex y in the tree T x .

•

If d = 1 then cs + y (T x [y]) = cs + y 1 (T x [y 1 ]). then cs y (T x [y]) ≤ 1, yielding a contradiction because d > 1. If otherwise cs + y 2 (T x [y 2 ]
) > 1 then we get cs y (T x [y]) < cs y 2 (T x [y 2 ]) + 1. In other words, there exists a monotone connected search strategy using at most cs y 2 (T x [y 2 ]) searchers for T x [y] starting from y. Let a ∈ {1, 2} be such that T x [y a ] is completely cleared before T x [y b ] is completely cleared, where b ∈ {1, 2}\{a}. Then let t be the first step of the strategy at which T x [y a ] becomes completely cleared. During all steps t , t ≤ t, at least one searcher must occupy a vertex outside T x [y a ] because otherwise {y, y a } would be recontaminated. Thus clearing T x [y a ] from y a has been achieved with strictly less than cs y 2 (T x [y 2 ]) searchers, a contradiction since cs + y

2 (T x [y 2 ]) > 1 insures that cs y 1 (T x [y 1 ]) ≥ cs y 2 (T x [y 2 ]
). This completes Case 2, and the proof of the lemma.

We remark that the above proof could become shorter (but also less self-contained) by making use of the results in Section 4.1. Note that a straightforward application of Lemma 6 enables to compute cs(T x ) in O(n) time, resulting in an O(n 2 )-time algorithm for computing cs(T ). We show that this complexity can be reduced to O(n), and, more importantly, that an optimal search strategy can also be computed in linear time.

Proof of Theorem 3. Let T be a tree. For every vertex x of T , we define the following labeling λ x of the edges incident to x. Let e = {x, y} be an edge incident to x. If y is a leaf, then λ x (e) = 1. Otherwise, let y 1 , . . . , y d be the d ≥ 1 neighbors of y in T distinct from x. If d = 1, we define λ x (e) = λ y ({y, y 1 }). If d > 1, then assume, w.l.o.g., that λ y ({y, y i }) ≥ λ y ({y, y i+1 }) for every i, 1 ≤ i < d. We then define λ x (e) = max{λ y ({y, y 1 }), λ y ({y, y 2 }) + 1}.

Note that every edge e = {x, y} is assigned two labels: λ x (e) and λ y (e). The following result is straightforward.

Claim 8. All edges can be labeled in O(n) time.

The following result establishes the relationship between the labels and the connected search numbers. Proof. The proof is by induction on the height h(y) of T x [y], i.e., on the length of the longest simple path from y to the leaves of T x [y]. The lemma holds for h(y) = 0, i.e., when y is a leaf, since then λ x (e) = cs + y (T x [y]) = 1. Let us assume that the lemma holds whenever 0 ≤ h(y) < k for k > 0, and let us consider the case when h(y) = k. Let y 1 , y

}) = max{cs + y 1 (T x [y 1 ]), cs + y 2 (T x [y 2 ]) + 1}.
Similarly, for d = 1, we get λ y ({y,

y i }) = cs + y 1 (T x [y 1 ]
). The claim thus follows by Lemma 6.

Consider now the following labeling µ of the vertices of T , which assigns to each vertex x a label µ(x) as follows. Let e 1 , e 2 , . . . , e d be the d edges incident to x in T . If d = 0 then µ(x) = 1. If d = 1 then µ(x) = λ x (e 1 ). If d ≥ 2 then assume, w.l.o.g., that λ x (e i ) ≥ λ x (e i+1 ) for each i, 1 ≤ i < d. Set µ(x) = max{λ x (e 1 ), λ x (e 2 ) + 1}.

Claim 10. For every vertex x of tree T , µ(x) = cs + x (T ).

Proof. To prove the claim, add a virtual vertex x to T and connect x to x, resulting in a tree T . Let λ be the edge-labeling in T . By definition, we have µ(x) = λ x ({x , x}). In view of Claim 9, we get µ(x) = cs + x (T x [x]). It follows that µ(x) = cs + x (T ).

It follows from Claim 8 that all µ(x)'s can be computed in O(n) time. Therefore, the connected search number of every tree T can be compute in linear time. Indeed, unless T is reduced to a single vertex, we have cs x (T ) = cs + x (T ) for every vertex x of T . We now show that an optimal monotone connected search strategy can also be computed in linear time.

Given a tree T and the labelings {λ x , x ∈ V (T )} and µ, consider the connected search strategy S constructed as follows. Let x be such that µ(x) = min y µ(y). For each vertex y, order locally its incident edges in T according to the labels assigned by λ y listed in increasing order. A monotone connected search strategy of T x is obtained by starting with µ(x) searchers in x, and performing a tour in T x according to a depth-first search (DFS) traversal respecting the local ordering of the edges. That is, at vertex y, the edges e incident to y with smallest labels λ y (e) are visited first. During this tour, the searchers are moved according to two simple rules:

• when moving from a vertex y to one of its children, z, slide λ y ({y, z}) searchers along {y, z} from y to z;

• when returning from z to y, slide these λ y ({y, z}) searchers from z back to y along {y, z}.

The following claim follows from a simple induction on the depth of the tree once we have observed that when sliding λ y ({y, z}) searchers along {y, z} from y to z, we actually move cs + z (T x [z]) searchers to z (cf. Claim 9). This number of searchers is sufficient to clear T x [z] from z in a connected monotone way.

Claim 11. The above search strategy is monotone, connected, and uses the optimal number of searchers.

Since the DFS traversal can be performed in O(n) time in n-vertex trees, this completes the proof of Theorem 3. (Note that the number of actions performed by the computed search strategy is O(n • cs(T )) because searchers are actually moved one by one in the search strategy; nevertheless the computed strategy can be coded compactly in O(n) time and space).

Note that, as opposed to what was claimed in [START_REF] Barrière | Capture of an intruder by mobile agents[END_REF], Theorem 3 does not trivially extend to the weighted version of the problem for which clearing an edge may require more than one searcher, and guarding a node may also require more than one searcher (see, e.g., [START_REF] Huc | Conception de Réseaux Dynamiques Tolérants aux Pannes[END_REF], page 111 for a counterexample). In fact, it is known [START_REF] Mihai | Pathwidth is NP-hard for weighted trees[END_REF] that weighted versions of the pathwidth problem are NP-hard even for the case of trees.

Concluding Remarks and Open Problems

In this paper we initiated the study of the complexity of the main variant of the graph searching problem under the connectivity demand. To conclude, we first discuss an important byproduct of the design of our algorithm for trees.

Horton-Strahler number. The property satisfied by the connected search number, as stated in Lemma 6, is precisely the one defining the so-called Horton-Strahler number, originally proposed in hydrology by Horton [START_REF] Horton | Erosional development of streams and their drainage basins: hydrophysical approach to quantitative morphology[END_REF] and Strahler [START_REF] Strahler | Hypsometric (area-altitude) analysis of erosional topology[END_REF][START_REF] Strahler | Quantitative analysis of watershed geomorphology[END_REF]. The Horton-Strahler number was initially defined as a measure of the propensity of a river to flood. It later appeared in many different contexts, including register allocation [START_REF] Flajolet | The number of registers required for evaluating arithmetic expressions[END_REF], mathematical biology [START_REF] Borchert | Bifurcation ratios and the adaptive geometry of trees[END_REF][START_REF] Horsfield | Some mathematical properties of branching trees with application to the respiratory system[END_REF] (concerning the study of bifurcations in natural trees and in the respiratory system), and, recently, social networks [START_REF] Arenas | Community analysis in social networks[END_REF]. The design of our linear-time algorithm for computing the connected search number cs(T ) of a tree T is actually based on the fact that the "rooted" connected search number cs x (T ) is precisely the Horton-Strahler number of a river with shape T , and whose mouth is vertex x.

Interestingly enough, the edge-labeling λ and the vertex-labeling µ used in the design of our algorithm shows that the Horton-Strahler number of a river T depends on the shape of the river basin modeled by T , but not much on the position of the mouth. (Indeed, it is easy to check that the labeling µ satisfies |µ(x)µ(y)| ≤ 1 for every two vertices x and y.) This observation holds for all hierarchical structures modeled by trees, such as the ones modeling arithmetical evaluations, or the ones modeling the hierarchical structure of social networks. Although all these trees are inherently rooted, only the structure of the tree actually matters, while the position of the root has almost no impact on the Horton-Strahler number.

Perhaps more interesting, the notion of connected search number may serve as a generalization of the Horton-Strahler number to arbitrary structures (i.e., graphs), beyond the simple case of trees. Determining what could be the interpretation of such a generalization in the framework of complex hydrological systems like swamps is an intriguing question (although is beyond the competences of the authors). Moreover, it would be of high interest to compute and compare the connected search numbers of various types of social networks. For instance, a small connected search number may indicate that information can be spread from one source to everyone while simultaneously using only few people as transmitters at each step. Conversely, a large connected search number may rather indicate that a rumor cannot spread in the network if less than a certain number of people are simultaneously acting as propagators.

Open problems. We conclude with a several open problems.

• Is it true that for any connected graph G, cs(G)/s(G) ≤ 2?

• It is not hard to show that deciding if cs(G) ≤ k for some k is NP-hard. We do not know if the problem belongs to NP and this is another open question. Let us remark, that by the result of Yang et al. [START_REF] Yang | Sweeping graphs with large clique number[END_REF], an optimal search strategy can use recontamination.

• The graph searching problem is fixed parameter tractable with a standard parameterization by the number of searchers. For connected search problem we even do not know if cs(G) ≤ k can be decided in polynomial time when k is not part of the input. Can it be that the problem is NP-hard already for small values of k like k = 3 or 4?

Final remarks. While this paper was under review, Dariusz Dereniowski solved the first open question stated in this paper, by proving that, for any connected graph G, cs(G)/s(G) ≤ 2 [START_REF] Dereniowski | From pathwidth to connected pathwidth[END_REF]. Moreover, the same author also proved that the weighted version of the problem is strongly NP-hard, even in the case of trees [START_REF] Dereniowski | Connected searching of weighted trees[END_REF].

  an e-cut is defined as the pair {E

2 Figure 1 :

 21 Figure1: A graph and one of its branch decompositions, of width 3.

Figure 1 :

 1 Figure 1: A graph and one of its branch decompositions, of width 3.

Figure 2 :

 2 Figure 2: Replacing quartets in Make-it-Connected

9

 9

Figure 2 :

 2 Figure 2: Replacing quartets in Make-it-Connected

Figure 3 :

 3 Figure 3: Algorithm Make-it-Connected

Claim 9 .

 9 For every edge e = {x, y} of T , we have λ x (e) = cs + y (T x [y]).

  and thus the smallest of the two boundaries is of size ≤ k. If (A 1 , A 2 , B 2 , B 1 ) is not a quartet, then assume, w.l.o.g., that ∂(A 1 , B 2

  2 , . . . , y d be the d ≥ 1 children of y in T x [y], where, w.l.o.g., λ y ({y, y i }) ≥ λ y ({y, y i+1 }). By definition of λ x , if d > 1 then λ x ({x, y}) = max{λ y ({y, y 1 }), λ y ({y, y 2 }) + 1}.For every i, 1 ≤ i ≤ d, the height of T y [y i ] is h(y i ) < k. Thus, by induction hypothesis, λ y ({y, y i

(2) ⇒ (3): We first claim that mcs(D k ) ≥ k + 1. For this, we prove that, for any connected search strategy in D k , there is a step in which at least k + 1 searchers are required for a monotone search of T . As this is obvious when k = 1, we assume that k > 1.

Acknowledgments. Many thanks to Binh Minh Bui Xuan for attracting our attention to the Horton-Strahler number of trees.

Lemma 4. Let T be a tree and e be an edge of it. Let also T be the tree created if we contract e in T . Then mcs(T ) ≤ mcs(T ).

Proof. Let w e be the vertex created in T after contracting e = {v, u}. Given a monotone search strategy S for T that uses ≤ k searchers with n steps, we make a strategy S for T as follows: Suppose that e is cleaned at the ith step of this strategy. Then, the new strategy is constructed by taking the first i -1 steps of S followed by the last ni -1 steps of S and then replacing each action concerning v or u with a same type action concerning w e . It is easy to verify that the new strategy is monotone and that it uses at most k searchers.

Lemma 5. For any tree T and k ≥ 1, the following three properties are equivalent:

(1) T is not a (k -1)-caterpillar;

(2) D k T ;

(3) cs(T ) ≥ k + 1.

Proof. (1) ⇒ (2): We start by a preliminary statement. Let T be a tree and v be a vertex of T such that B k v T , k ≥ 1. We claim that T is a (k -1)-caterpillar and v is an extremity of its spine. The proof of that claim is by induction on k. If B 1 v T then clearly T is a path with extremity v. If k > 1 and there is a vertex v such that B k v T , then there are two cases. If B k-1 v T , then by induction hypothesis, T is a (k -2)-caterpillar with v as the first vertex of the spine. If B k-1 v T , then let S be the set of vertices w such that B k-1 w T v [w]. S induces a path starting at v, and all the connected components of T -S are (k -2)-caterpillars, in which the corresponding spine starts at the vertex adjacent to one of the vertices of S in T . Indeed, if z / ∈ S and z is adjacent to w ∈ S, then

To complete the proof of the statement, it is enough to prove that if D k T , then T contains a vertex v such that B k v T . Towards a contradiction, assume that for every vertex v of T , B k v T . There is a vertex z with two neighbors, z 1 and z 2 , such that

In both cases, we get D k T , a contradiction.

). Hence the lemma holds for d = 1. So assume now that d > 1. We consider two cases.

Case 1: cs

In that case, cs y 1 (T x [y 1 ]) searchers suffice to clear T x [y] starting from y, by clearing T x [y 1 ] last among the children of y, and by letting one searcher occupying vertex y while the other subtrees are successively cleared. Indeed, every subtree T x [y i ] with i > 1 requires at most

), and thus cs + y (T x [y]) ≤ cs + y 1 (T x [y 1 ]). To prove equality, assume that cs + y (T x [y])

). First, we consider two sub-cases for proving cs + y (T x [y]) ≤ cs + y 2 (T x [y 2 ]) + 1.