Monotonicity of non-deterministic graph searching

AbstractIn graph searching, a team of searchers are aiming at capturing a fugitive moving in a graph. In the initial variant, called invisible graph searching, the searchers do not know the position of the fugitive until they catch it. In another variant, the searchers permanently know the position of the fugitive, i.e. the fugitive is visible. This latter variant is called visible graph searching. A search strategy that catches any fugitive in such a way that the part of the graph reachable by the fugitive never grows is called monotone. A priori, monotone strategies may require more searchers than general strategies to catch any fugitive. This is however not the case for visible and invisible graph searching. Two important consequences of the monotonicity of visible and invisible graph searching are: (1) the decision problem corresponding to the computation of the smallest number of searchers required to clear a graph is in NP, and (2) computing optimal search strategies is simplified by taking into account that there exist some that never backtrack.Fomin et al. [F.V. Fomin, P. Fraigniaud, N. Nisse, Nondeterministic graph searching: From pathwidth to treewidth, in: Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, MFCS’05, 2005, pp. 364–375] introduced an important graph searching variant, called non-deterministic graph searching, that unifies visible and invisible graph searching. In this variant, the fugitive is invisible, and the searchers can query an oracle that permanently knows the current position of the fugitive. The question of the monotonicity of non-deterministic graph searching was however left open.In this paper, we prove that non-deterministic graph searching is monotone. In particular, this result is a unified proof of monotonicity for visible and invisible graph searching. As a consequence, the decision problem corresponding to non-deterministic graph searching belongs to NP. Moreover, the exact algorithms designed by Fomin et al. do compute optimal non-deterministic search strategies