Briefly, the problem of graph searching is stated as a game where a team of a certain number of searchers aims to capture a fugitive moving in a graph, either in an invisible way (the searchers ignore the position of the fugitive until they catch it) or in a visible way (the searchers are informed about the position of the fugitive at each moment of the search process). The fugitive is caught when a searcher is placed at the vertex it occupies and searchers are placed at all neighbor vertices.

The framework of the research, preliminary definitions, some already-published results in this area, and related work are presented in the first two sections of the paper. In order to prove the monotonicity of nondeterministic graph searching, an auxiliary structure called search tree is introduced in the final part of the second section.

Section 3 contains the authors’ main new contributions. Theorem 2 establishes that, “from any winning q-program using at most k searchers in a graph G, [it is possible to] build a q-search-tree of width at most k for G.” Then, Lemma 3 shows that this q-search-tree can be transformed into a monotone one without increasing its width, and Lemma 5 establishes that “any monotone q-search-tree, of width k, of a graph G can be transformed into a q-branched tree decomposition, of width at most k-1.” Using this construction and invoking a previously published result, the monotonicity property of nondeterministic graph searching is concluded in the final part of the paper.

In my opinion, aside from their importance from a theoretical point of view, the developments could prove useful in developing efficient tools for detecting intrusions in networks.