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

Search Nedrilad ::

Custom Search