Search strategies find largest safe areas in graphs with few searchers
Searching subgraphs
Data Structures and Algorithms
Summary
The paper looks at how to catch an invisible and very fast intruder hiding in a network or graph using a limited number of searchers. When there are not enough searchers to clear the entire network, the authors study how to clear the biggest part possible while keeping it connected. They also consider a tougher case where some parts of the network might never be cleared, requiring strategies that avoid letting the intruder come back. The authors find both problems are hard in general, but they provide efficient algorithms for special cases like tree-shaped graphs.
What this means in practice
- •For network security teams: Optimize limited monitoring resources to guard the largest connected portion of communication networks from hidden intruders.
- •For robot path planners: Plan efficient movements of limited robots to scan and secure the largest connected area in environment graphs under resource constraints.
Authors
Dariusz Dereniowski, Boting Yang
Abstract
We consider graph search models, in which an invisible, omniscient and fast intruder can hide anywhere in the graph, and the goal is to design a \emph{search strategy} composed of a sequence of movements of \emph{searchers} that guarantees the capture of the intruder regardless of its actions. Our point of departure is the connected search model in which the cleared subgraph is always connected during the search process. In this paper, we initiate the study of the subgraph searching problems which arise from the following question: what happens if the number of searchers available is not sufficient to clear a given graph $G$? We propose an approach in which one wants to clear in a connected way as large subgraph as possible with the given $k$ searchers. In this context we study two problems: one problem, called the \emph{subgraph search}, is to find the maximum-sized subgraph whose search number is at most $k$, and the other one, called the \emph{protected subgraph search}, is to perform a partial search on $G$ leading to as many cleared edges as possible. Informally speaking, the difference lies in the fact that in the latter a recontamination may come from an edge never to be cleared and hence the partial search strategy needs to avoid such recontaminations. Having proved that both problems are computationally hard in general, we give efficient algorithms for $n$-vertex trees: an $\bigo(\min\{kn, n \log n\})$ time algorithm for the subgraph search and an $\bigo(\min\{2^{6k}kn, n^{8.571} \log n\})$ time algorithm for the protected subgraph search.