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