Game Development Reference
In-Depth Information
by three parallel edges, then the edge search number of G is one more than
the node search number of G .
LaPaugh [1993] 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 [1986] establish monotonicity for the node searching game.
Bienstock and Seymour [1991] 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
[2003]. 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. [1988] 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 [1993] 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 [2008]. We will review this proof method in
Section 7.4 below.
Arnborg et al. [1987] 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
Search Nedrilad ::




Custom Search