Game Development Reference
InDepth Information
treedecomposition yields a recursive decomposition of a graph into small sub
graphs and this allows us to use the same dynamic programming approaches
to solve problems on graphs of small treewidth that can be employed on trees.
Determining the treewidth of a graph is NPcomplete as shown by Arnborg
et al. [1987], but there is an algorithm, due to Bodlaender [1996], which, given
a graph
G
computes an optimal treedecomposition in time
(2
p
(tw(
G
))
),
for some polynomial
p
. Combining this with dynamic programming yields a
powerful tool to solve NPhard problems on graph classes of small treewidth.
See Bodlaender [1997, 1998, 2005] for surveys including a wide range of
algorithmic examples.
To help gain some intuition about treedecompositions we establish some
simple properties and a normal form for treedecompositions. We first agree
on the following notation. From now on we will consider the tree
T
of a tree
decomposition to be a rooted tree, where the root can be chosen arbitrarily.
If
T
is a rooted tree and
t ∈ V
(
T
) then
T
t
is the subtree
rooted at t
, i.e., the
subtree containing all vertices
s
such that
t
lies on the path from the root
of
T
to
s
.
O
·
G

Lemma 7.36
If G has a treedecomposition of width k then it has a
treedecomposition
(
T,
(
B
t
)
t∈V
(
T
)
)
of width k so that if
{
s, t
}∈
E
(
T
)
then
B
s
⊆
B
t
and B
t
⊆
B
s
.
Proof
Let
T
:= (
T,
(
B
t
)
t∈V
(
T
)
) be a treedecomposition such that
B
s
⊆
B
t
for some edge
E
(
T
). Then we can remove
s
from
T
and make all
neighbours of
s
other than
t
neighbours of
t
. Repeating in this way we generate
a treedecomposition of the same width with the desired property.
{
s, t
}∈
Definition 7.37
Let
G
be a graph. A
separation
of
G
is a triple (
A, S, B
)
of nonempty sets such that
A
∪
S
∪
B
=
V
(
G
) and there is no path in
G
\
S
from a vertex in
A
to a vertex in
B
.
Lemma 7.38
Let
T
:= (
T,
(
B
t
)
t∈V
(
T
)
)
be a treedecomposition of a graph
G and let e
:=
{
s, t
}∈
E
(
T
)
.LetT
s
be the subtree of T
−
e containing s
and let T
t
be the subtree of T
−
e containing t. Finally, let S
:=
B
s
∩
B
t
.
Then
(
B
(
T
t
)
\
S, S, B
(
T
s
)
\
S
)
is a separation in G.
Exercise.
Prove this lemma.
Definition 7.39
A treedecomposition
T
:= (
T,
(
B
t
)
t∈V
(
T
)
) of a graph
G
is
in
normal form
if whenever
t ∈ V
(
T
) is a node and
C
is a component of
G\B
t
then there is exactly one successor
t
C
of
t
in
T
such that
V
(
C
)=
s∈V
(
T
t
)
B
s
.
Search Nedrilad ::
Custom Search