Game Development Reference

In-Depth Information

:= (
T,
(
B
t
)
t∈V
(
T
)
) be a tree-decomposition of

G
of width at most
k
. By Lemma 7.40, we can assume that

Towards the converse, let

T

is in normal

form. But then it is easily seen that (
T,cops, robber
) with
cops
(
t
):=
B
t
and

robber
((
t, s
)) :=
B
(
T
s
)

T

\

B
t
is a monotone strategy tree, where
T
s
is the

component of
T

−

(
t, s
) containing
s
.

The previous lemma together with the monotonicity of the visible Cops and

Robber game proved in Theorems 7.24 and 7.34 imply the following corollary.

Note that it is the monotonicity of the game that brings the different concepts

- winning strategies, tree-decompositions, obstructions - together to form a

uniform characterisation of tree-width and search numbers. This is one of

the reasons why monotonicity has been studied so intensively especially in

structural graph theory.

Corollary 7.42
For all graphs G:
tw(
G
)=bw(
G
)=cw(
G
)
−
1
, where

bw(
G
)
denotes the bramble width and cw
(
G
)
the minimal number of cops

required to win the visible cops and robber game.

A similar characterisation can be given for the invisible Cops and Rob-

ber Game. A
path-decomposition
of a graph
G
is a tree-decomposition

(
T,
(
B
t
)
t∈V
(
T
)
)of
G
where
T
is a simple path. The
path-width
of a graph is

the minimal width of a path-decomposition of
G
. Similarly as above we can

show that the path-width pw(
G
) of a graph is just one less than the minimal

number of cops required to catch an invisible robber (with a monotone

strategy) on
G
. The obstructions for path-width corresponding to brambles

are called
blockages
. See Bienstock et al. [1991] for details.

7.7 Complexity of graph searching

In this section we study the complexity of computing the least number of

searchers required to win a given graph searching game. As usual we will

view this as a decision problem asking for a given game and a number
k

whether
k
searchers can catch a fugitive or whether they can even do so with

a monotone strategy.

We have already stated a number of complexity results in Section 7.3. The

aim of this section is to establish much more general results valid for almost

all graph searching games within our framework.

Note that all variations of graph searching games described in this chapter

- as games played on undirected, directed or hypergraphs, inert variants,

etc. - can all be described by suitably defining the relation

S

and the

function

F

in a graph searching game (
V,

S

,

F

,c
). The only exception is the

Search Nedrilad ::

Custom Search