Game Development Reference
In-Depth Information
tree-decomposition 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 tree-width that can be employed on trees.
Determining the tree-width of a graph is NP-complete as shown by Arnborg
et al. [1987], but there is an algorithm, due to Bodlaender [1996], which, given
a graph G computes an optimal tree-decomposition in time
(2 p (tw( G ))
),
for some polynomial p . Combining this with dynamic programming yields a
powerful tool to solve NP-hard problems on graph classes of small tree-width.
See Bodlaender [1997, 1998, 2005] for surveys including a wide range of
algorithmic examples.
To help gain some intuition about tree-decompositions we establish some
simple properties and a normal form for tree-decompositions. 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 sub-tree rooted at t , i.e., the
sub-tree 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 tree-decomposition of width k then it has a
tree-decomposition ( 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 tree-decomposition 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 tree-decomposition 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 non-empty 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 tree-decomposition of a graph
G and let e :=
{
s, t
}∈
E ( T ) .LetT s be the sub-tree of T
e containing s
and let T t be the sub-tree 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 tree-decomposition 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 .