Game Development Reference
InDepth 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 treewidth rather than winning
strategies for the cops and is often referred to as the
treewidth 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 graphdecompositions
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
treewidth
.
The concept of
treewidth
was developed by Robertson and Seymour [1982
] as part of their celebrated graph minor project, even though concepts such
as
partial ktrees
, which subsequently have been shown to be equivalent to
treewidth, were known before.
Definition 7.35
Let
G
be a graph. A
treedecomposition
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 nonempty subtree 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
treewidth
of
G
is the minimal width of a treedecomposition of
G
.
We will frequently use the following notation: if
S
⊆
T
is a subtree of
T
then
B
(
S
):=
.
From a graph structural point of view, the treewidth 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
)
}
Search Nedrilad ::
Custom Search