Game Development Reference
In-Depth 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 non-monotone 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 (non-empty) 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