Exclusive Graph Searching

This paper tackles the well known graph searching problem, where a team of searchers aims at capturing an intruder in a network, modeled as a graph. This problem has been mainly studied for its relationship with the pathwidth of graphs. All variants of this problem assume that any node can be simultaneously occupied by several searchers. This assumption may be unrealistic, e.g., in the case of searchers modeling physical searchers, or may require each individual node to provide additional resources, e.g., in the case of searchers modeling software agents. We thus introduce and investigate exclusive graph searching, in which no two or more searchers can occupy the same node at the same time. As for the classical variants of graph searching, we study the minimum number of searchers required to capture the intruder. This number is called the exclusive search number of the considered graph. Exclusive graph searching appears to be considerably more complex than classical graph searching, for at least two reasons: (1) it does not satisfy the monotonicity property, and (2) it is not closed under minor. Moreover, we observe that the exclusive search number of a tree may differ exponentially from the values of classical search numbers (e.g., pathwidth). Nevertheless, we design a polynomial-time algorithm which, given any n-node tree T, computes the exclusive search number of T in time \(O(n^3)\). Moreover, for any integer k, we provide a characterization of the trees T with exclusive search number at most k. Finally, we prove that the ratio between the exclusive search number and the pathwidth of a graph is bounded by its maximum degree.

1. Note that, whenever exclusivity is not required, internality is not a strong constraint (difficult to overcome), since the jumping of one searcher from a node u to a node v can be replaced by sliding this searcher along a path from u to v. However, the combination of exclusivity and internality makes the problem much more difficult.

2. That is, \(s_i\) consists in either placing a searcher at a node of \(V(G) \setminus V(H)\), or removing a searcher from a node of \(V(G) \setminus V(H)\), or sliding a searcher along an edge in \(\{u,v\} \in E(G)\) where \(u,v \in V(G) \setminus V(H)\)

3. This constraint is only to avoid considering pathological cases when a sequence \({\mathcal {S}}\) starts from a state (I, F) and some edges of F are recontaminated before the first move of \({\mathcal {S}}\).

4. If \(|V(R^1)|< k-1\), then the strategy starts by placing one searcher at \(u_1\), then as much as possible searchers at the nodes of \(R^1\), then at the nodes of \(T^1_1\), of \(T^1_2\), and so on, until the k searchers are placed.

Authors and Affiliations

1. CNRS, Sorbonne Universités, UPMC Univ Paris 06, Paris, France

   Lélia Blin

2. Université d’Evry-Val-d’Essonne, Evry, France

   Lélia Blin

3. LIP6 UMR 7606, 4 place Jussieu, 75005, Paris, France

   Lélia Blin

4. LRI, CNRS, UMR-8623, Université Paris Sud, Orsay, France

   Janna Burman

5. Inria, Sophia Antipolis, France

   Nicolas Nisse

6. Univ. Nice Sophia Antipolis, CNRS, I3S, UMR 7271, Sophia Antipolis, France

   Nicolas Nisse

Corresponding author

Correspondence to Lélia Blin.

An extended abstract of this work has been presented in ESA 2013 [4].

Reprints and permissions