Game Development Reference
In-Depth Information
The searchers and the fugitive occupy vertices but a searcher not only controls
the vertex it occupies but also all of its neighbours. Again we can study the
visible and the invisible variant of the game.
Kreutzer and Ordyniak [2009] showed that there is a class
C
of graphs
such that for all G
∈C
2 searchers have a winning strategy on G but for
every k
such that no fewer than k searchers
are needed for a monotone winning strategy. A similar result has also been
shown for the visible case.
N
there is a graph G k ∈C
7.5 Obstructions
So far we have mostly studied strategies for the Searcher. However, if we want
to show that k searchers have no winning strategy in a graph searching game
G , then we have to exhibit a winning strategy for the fugitive. The existence
of a winning strategy for the fugitive on a graph searching game played
on an undirected graph G gives a certificate that the graph is structurally
fairly complex. Ideally, we would like to represent winning strategies for the
fugitive in a simple way so that these strategies can be characterised by
the existence of certain structures in the graph. Such structures have been
studied intensively in the area of graph decompositions and have come to be
known as obstructions .
In this section we will look at two very common types of obstructions,
called havens and brambles , which have been defined for numerous games.
We will present these structures for the case of the visible cops and robber
game played on an undirected graph.
We have already seen havens for the directed SCC game but here we will
define them for the undirected case.
Definition 7.30
Let G be a graph. A haven of order k in G is a function
h :[ V ( G )] ≤k
[ V ( G )] ≤k f ( X ) is a component
Pow( V ) such that for all X
of G
X and if Y
X then h ( Y )
h ( X ).
It is easily seen that if there is a haven of order k in G then the robber
wins against k cops on G .
Lemma 7.31 If h is a haven bramble of order k in a graph G then the
robber wins against k cops on G and conversely if the robber has a winning
strategy against k cops then there is a haven of order k in G.
An alternative way of formalising a robber winning strategy is to define