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