Game Development Reference
InDepth Information
Theorem 7.27
The visible SCC Cops and Robber game on directed graphs
is approximately monotone. More formally, if G is a directed graph, then for
all k,ifk cops can catch the robber on G then
3
k
+2
cops can catch the
robber with a monotone strategy.
The proof of this theorem relies on the concept of a
haven
, which is a
representation of a winning strategy for the robber. Essentially, the proof
idea is to iteratively construct a monotone winning strategy for 3
k
+ 2 cops,
starting from some initial position. If at some point of the construction we
cannot extend the monotone winning strategy then this will give us enough
information for constructing a haven of order
k
showing that the robber can
win against
k
cops even in the nonmonotone game.
Definition 7.28
Let
G
be a directed graph. A
haven of order
k
in
G
is
a function
h
:[
V
(
G
)]
≤k
[
V
(
G
)]
≤k
→
Pow(
V
) such that for all
X
∈
1
h
(
X
) is a (nonempty) strongly connected component of
G
−
X
and
2if
Y ⊆ X
then
h
(
Y
)
⊇ h
(
X
).
Let
G
be a directed graph. W.l.o.g. we assume that
G
is strongly connected.
Otherwise, we can search the components of
G
one by one.
Obviously, if
G
hasahavenoforder
k
then the robber wins against
k
cops
in the visible SCC game by always staying in the component
h
(
X
) whenever
the cops are on
X
. To prove the theorem it therefore su
ces to show that
if there is no haven of order
k
then at most 3
k
+ 2 cops have a monotone
winning strategy.
We are going to describe a monotone winning strategy for 3
k
+ 2 cops.
Throughout the proof,
W
will always denote the current robber space.
Initially, therefore, we set
W
:=
V
(
G
).
In their first move, the cops arbitrarily choose a set
Y
of 2
k
+ 1 vertices
on which they place the searchers. If for every set
Z
of
≤
k
vertices there is
a strong component
C
(
Z
)of
G
k
+ 1, then the
function
h
mapping any set
Z
with
Z
≤k
to
C
(
Z
) is a haven of order
k
.
For, any two
C
(
Z
) and
C
(
Z
) contain more than
\
Z
such that

Y
∩
V
(
C
)
≥
1
2
of the vertices in
Y
and
therefore must share a vertex.
Hence, if there is no such haven, then there must be a
Z
of
≤ k
vertices
such that no component
C
of
G \ Z
contains more than
k
vertices of
Y
.To
define the next step of the monotone winning strategy for the cops we choose a
vertex
w
W
arbitrarily and place additional cops on
Z
:=
Z
∪{
. At this
stage, no more than 3
k
+ 2 cops are on the board. Now let the robber choose
his next position, that is a strong component
C
of
G
∈
w
}
\
(
Y
∪
Z
) contained in
W
. Let
C
be the strong component of
G
\
Z
containing
C
. Clearly,
C
is also
Search Nedrilad ::
Custom Search