Game Development Reference
In-Depth Information
played on undirected and directed graphs. For, let G be an undirected graph
with some cops being on position X and let R be the robber space, i.e., the
component of G
X containing the robber. Now, for every Y
V ( G ), if
the Cop player places cops on X
Y and then removes them from Y again,
i.e., moves back to position X , then the robber space is exactly the same
space R as before. Intuitively, this is the reason why non-monotone moves
are never necessary in the undirected cops and robber game. For a game
played on directed graphs, this is not the case as the example above shows.
If X :=
Y and the robber
has moved to C L , the cops can be lifted from C R without the robber being
able to regain control of the lost vertices.
To see that the two variants of directed graph searching games presented
above are very different consider the class of trees with backedges as studied,
e.g., by Berwanger et al. [2006]. The idea is to take a tree and add an edge
from every node to any of its (direct or indirect) predecessors up to the root.
Then it is easily seen that two searchers su ce to catch a visible fugitive in
the SCC game on these trees but to catch the fugitive in the reachability
game we need at least as many cops as the height of tree. (It might be a
good exercise to prove both statements.) Hence, the difference between the
two game variants can be arbitrarily large. On the other hand, we never need
more searchers to catch the fugitive in the SCC game than in the reachability
game as every move allowed to the fugitive in the latter is also a valid move
in the former.
The visible SCC game has been introduced in connection with directed
tree-width by Johnson et al. [2001]. Barat [2006] studies the invisible reach-
ability game and established its connection to directed path-width . Finally,
the visible reachability game was explored by Berwanger et al. [2006] and its
inert variant by Hunter and Kreutzer [2008]. See also Hunter [2007].
As we have seen above, the visible, invisible and inert invisible graph
searching games as well as their edge and mixed search variants are all
monotone on undirected graphs. For directed graphs the situation is rather
different. Whereas Barat [2006] proved that the invisible reachability game
is monotone, all other game variants for directed graphs mentioned here
have been shown to be non-monotone. For the SCC game this was shown
by Johnson et al. [2001] for the case of searcher monotonicity and by Adler
[2007] for fugitive monotonicity. However, Johnson et al. [2001] proved that
the visible SCC game is at least approximately monotone . We will review the
proof of this result in Section 7.4 below.
The visible reachability game as well as the inert reachability game were
shown to be non-monotone by Kreutzer and Ordyniak [2008].
6 , 7
and Y := C R then once the cops go on X
Search Nedrilad ::

Custom Search