Game Development Reference
In-Depth Information
We refrain from giving the proof here and refer to Seymour and Thomas
[1993] (where brambles were called screens) or the excellent survey by Reed
[1997].
The previous result was stated in terms of tree-width rather than winning
strategies for the cops and is often referred to as the tree-width duality
theorem . A very general way of establishing duality theorems of this form
was studied by Amini et al. [2009], Adler [2009] and Lyaudet et al. [2009]
and by Fomin and Thilikos [2003] for the case of an invisible robber.
7.6 An application to graph-decompositions
As outlined in the introduction, graph searching games have found various
applications in a number of areas in computer science. Among those, their
application in structural graph theory has been a particularly driving force
behind developments in graph searching. We demonstrate this by deriving
a close connection between undirected cops and robber games and a graph
structural concept called tree-width .
The concept of tree-width was developed by Robertson and Seymour [1982
-] as part of their celebrated graph minor project, even though concepts such
as partial k-trees , which subsequently have been shown to be equivalent to
tree-width, were known before.
Definition 7.35
Let G be a graph. A tree-decomposition of G is a pair
T
:= ( T, ( B t ) t∈V ( T ) ) where T is a tree and B t
V ( G ) for all t
V ( T ) such
that
1 for all v
V ( G ) the set
{
t : v
B t }
induces a non-empty sub-tree of T
and
2 for every edge e :=
{
u, v
}∈
E ( G ) there is a t
V ( T ) such that
{
u, v
}⊆
B t .
The width w (
T
)of
T
is
w (
T
):=max
{|
B t
|
: t
V ( T )
}−
1 .
The tree-width of G is the minimal width of a tree-decomposition of G .
We will frequently use the following notation: if S
T is a sub-tree of T
then B ( S ):=
.
From a graph structural point of view, the tree-width of a graph measures
the similarity of a graph to being a tree. However, the concept also has
immense algorithmic applications as from an algorithmic point of view a
{
v : v
B l for some l
V ( S )
}