Connected graph searching in chordal graphs

Graph searching was introduced by Parson [T. Parson, Pursuit-evasion in a graph, in: Theory and Applications of Graphs, in: Lecture Notes in Mathematics, Springer-Verlag, 1976, pp. 426–441]: given a “contaminated” graph GG (e.g., a network containing a hostile intruder), the search number  s(G) of the graph GG is the minimum number of searchers needed to “clear” the graph (or to capture the intruder). A search strategy is connected   if, at every step of the strategy, the set of cleared edges induces a connected subgraph. The connected search number cs(G) of a graph GG is the minimum kk such that there exists a connected search strategy for the graph GG using at most kk searchers. This paper is concerned with the ratio between the connected search number and the search number. We prove that, for any chordal graph GG of treewidth tw(G), cs(G)/s(G)=O(tw(G)). More precisely, we propose a polynomial-time algorithm that, given any chordal graph GG, computes a connected search strategy for GG using at most (tw(G)+2)(2s(G)−1) searchers. Our main tool is the notion of connected   tree-decomposition. We show that, for any connected graph GG of chordality kk, there exists a connected search strategy using at most (tw(G)⌊k/2⌋+2)(2s(T)−1) searchers where TT is an optimal tree-decomposition of GG.