Game Development Reference
by three parallel edges, then the edge search number of G is one more than
the node search number of G .
LaPaugh  proved that the edge searching game is monotone thereby
giving the first monotonicity proof for a graph searching game. Using the
correspondence between edge searching and node searching, Kirousis and
Papadimitriou  establish monotonicity for the node searching game.
Bienstock and Seymour  consider a version of invisible graph searching,
called mixed searching , where the searcher can both slide along an edge or
move to other nodes clearing an edge as soon as both endpoints are occupied.
They give a simpler monotonicity proof for this type of game which implies
the previous two results.
A very general monotonicity proof for games with an invisible robber
based on the concept of sub-modularity was given by Fomin and Thilikos
. We will present an even more general result using sub-modularity in
Section 7.4 below.
Using a reduction from the Min-Cut Into Equal-Sized Subsets prob-
lem, Megiddo et al.  showed that edge searching is NP-complete. Using
the correspondence between edge and node searching outlined above, this
translates into NP-completeness of the node searching variant, i.e., the Invis-
ible Cops and Robber Game defined above.
7.3.3 Visible Robber games
We have already introduced the visible cops and robber game above. This
game was studied by Seymour and Thomas  in relation to tree-width, a
connection which we will present in more depth in Section 7.6. In this paper
they introduce a formalisation of the robber strategies in terms of screens ,
nowadays more commonly referred to as brambles , and use this to prove
monotonicity of the visible cops and robber game. A monotonicity proof
unifying this result and the results obtained for invisible robber games has
been given by Mazoit and Nisse . We will review this proof method in
Section 7.4 below.
Arnborg et al.  proved by a reduction from the Minimum Cut
Linear Arrangement problem that determining for a given graph the
minimal k such that G can be represented as a partial k-tree is NP-complete.
This number is equal to the tree-width of G and therefore deciding the
tree-width of a graph is NP-complete. We will see in Section 7.6 that the
minimal number of searchers, called the visible search width of G , required
to catch a visible fugitive in the visible Cops and Robber game on a graph G