Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Treewidth
Dynamic Programming on Trees
Outline
1 Treewidth
Dynamic Programming on Trees
Treewidth: Generalizing Trees
Computing Treewidth
Treewidth
Dynamic Programming on Trees
The Party Problem
PARTY PROBLEM
Problem: Invite some colleagues to a party.
Maximize: The total fun factor of the invited people.
Constraint: Everyone should be having fun.
Do not invite a colleague and his direct boss at the same time!
Treewidth
Dynamic Programming on Trees
The Party Problem
PARTY PROBLEM
Input: A tree with weights on the
vertices.
Question: Find an independent set of
maximum weight.
3
5
4 4 6
6
Treewidth
Dynamic Programming on Trees
The Party Problem
PARTY PROBLEM
Input: A tree with weights on the
vertices.
Question: Find an independent set of
maximum weight.
3
5
4 4 6
6
Treewidth
Dynamic Programming on Trees
Dynamic Programming on trees (or tree-like
structures)
A dynamic programming algorithm on a tree (or a tree-like
structure) usually computes a set of records for every node
of the tree in a bottom-up manner, i.e., we first compute the
records for the leaves of the tree and then work our way up
the tree.
Informally, a record is a compact representation of partial
solutions, i.e., solutions obtained for the subtree below the
current node.
Ideally, the solution for the whole problem can be directly
inferred from the set of records computed for the root of the
tree.
Treewidth
Dynamic Programming on Trees
Example: Solving the party problem
Here and in the sequel we use the following notation: Let T be
a (rooted) tree and t ∈ V(T), then:
T(t) is the subtree of T rooted at t;
R(t) denotes the set of records for the tree node t.
Treewidth
Dynamic Programming on Trees
Solving the party problem: The Records
For the PARTY PROBLEM a record is a pair (inc, w) where inc is
a boolean value and w is a real value. The semantics of a
record for a tree node t ∈ V(T) is as follows:
(0, w) ∈ R(t) iff w is the maximum weight of an
independent set of T(t) that does not contain v;
(1, w) ∈ R(t) iff w is the maximum weight of an
independent set of T(t);
Clearly, the solution of the party problem can be easily obtained
from R(r) as the weight w such that (1, w) ∈ R(r).
Treewidth
Dynamic Programming on Trees
Solving the party problem: Computing the Records
We need to show that we can compute the records for the
PARTY PROBLEM for every node of the tree in a bottom-up
manner, i.e., we need to show that the set of all records can be
computed:
(1) For the leave nodes of the tree.
(2) For every inner node of the tree (given the set of records of
all its children).
Treewidth
Dynamic Programming on Trees
Solving the party problem: Computing the Records
For the PARTY PROBLEM this can be done as follows (here T is
the given tree with weight function w and t ∈ V(T)):
(1) If t is a leave node of T then R(t) := {(0, 0), (1, w(t))}.
(2) If t is an inner node of T with children t1, . . . , tl, then
R(t) := {(0, wo), (1, wi)} where
wo := { w : 1 ≤ i ≤ l and (1, w) ∈ R(ti) }
and
wi := max{wo, w(t) + { w : 1 ≤ i ≤ l and (0, w) ∈ R(ti) }.
Treewidth
Dynamic Programming on Trees
Solving the party problem: Computing the Records
For the PARTY PROBLEM this can be done as follows (here T is
the given tree with weight function w and t ∈ V(T)):
(1) If t is a leave node of T then R(t) := {(0, 0), (1, w(t))}.
(2) If t is an inner node of T with children t1, . . . , tl, then
R(t) := {(0, wo), (1, wi)} where
wo := { w : 1 ≤ i ≤ l and (1, w) ∈ R(ti) }
and
wi := max{wo, w(t) + { w : 1 ≤ i ≤ l and (0, w) ∈ R(ti) }.
This gives a polynomial time algorithm for the PARTY PROBLEM
on trees!
Treewidth
Treewidth: Generalizing Trees
Outline
1 Treewidth
Dynamic Programming on Trees
Treewidth: Generalizing Trees
Computing Treewidth
Treewidth
Treewidth: Generalizing Trees
Treewidth
Treewidth
Treewidth: Generalizing Trees
Introduction
Treewidth is a measure of how “tree-like” a graph is.
Treewidth has become a very successful notion both in
structural and algorithmic graph theory.
Almost every natural problem on graphs becomes solvable
in polynomial time on graphs of bounded treewidth, usually
even fixed-parameter tractable when parameterized by
treewidth.
Algorithms on graphs of bounded treewidth usually follow
the general dynamic programming approach that we
presented for trees.
Treewidth is usually defined in terms of a so called
tree-decomposition (although many different alternative
definitions exist).
Treewidth
Treewidth: Generalizing Trees
Definition
A tree decomposition of a graph G is a pair (T, X) where T is a
tree and X = { X(t) : t ∈ V(T) } is set of subsets of V(G) such
that:
T1 For every {u, v} ∈ E(G) there is a node t ∈ V(T) such that
{u, v} ∈ X(t).
T2 For every v ∈ V(G), the subgraph of T induced by
X−1(v) := { t ∈ V(T) : v ∈ X(t) } is non-empty and
connected.
To distinguish between vertices of G and T, the vertices of T
are called nodes. The sets X(t) are also called the bags of the
tree decompositon.
The width of a tree decomposition is (maxt∈V(T) |X(t)|) − 1 and
the treewidth of G is the smallest width of any tree
decompositon of G.
Treewidth
Treewidth: Generalizing Trees
Example
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Example
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Example
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Example
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Example
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Basic Properties
A tree decomposition of a graph G is a pair (T, X) where T is a
tree and X = { X(t) : t ∈ V(T) } is set of subsets of V(G) such
that:
T1 For every {u, v} ∈ E(G) there is a node t ∈ V(T) such that
{u, v} ∈ X(t).
T2 For every v ∈ V(G), the subgraph of T induced by
X−1(v) := { t ∈ V(T) : v ∈ X(t) } is non-empty and
connected.
Property T2 is often called the “connectedness condition” and
can be equivalently formulated as:
T2’ For every t, t , t ∈ V(T) such that t lies on the unique
path between t and t in T it holds that:
X(t) ∩ X(t ) ⊆ X(t ). Furthermore, every vertex of G is
contained in some bag of T.
Treewidth
Treewidth: Generalizing Trees
Basic Properties
Observation (-1)
Let G be a graph. Then tw(G) ≤ |V(G)| − 1.
Observation (0)
tw(G) = 0 iff G contains no edges.
Observation (1)
Let H be a subgraph of a graph G. Then tw(H) ≤ tw(G).
Proof:
Let (T, X) be a tree decomposition of G. Then (T, X ) such that
X(t) := X(t) ∩ V(H) for every t ∈ V(T) is a tree decomposition
of H whose width is at most as high as the width of (T, X).
Treewidth
Treewidth: Generalizing Trees
Basic Properties
Observation (2)
Let A and B be 2 graphs and let G be the disjoint union of A
and B. Then tw(G) = max{tw(A), tw(B)}.
Proof:
Let (TA, XA) and (TB, XB) be tree decompositions of A and B,
respectively. Then (T, X) such that:
T is the disjoint union of TA and TB plus an addional node
r that is connected to one node of TA and one node of TB.
X(r) := ∅, X(t) := X(t)A for every t ∈ V(TA), and
X(t) := X(t)B for every t ∈ V(TB).
is a tree decomposition of G of width at most
max{tw(A), tw(B)}.
Treewidth
Treewidth: Generalizing Trees
Basic Properties
Observation (2)
Let A and B be 2 graphs and let G be the disjoint union of A
and B. Then tw(G) = max{tw(A), tw(B)}.
Corollary (1)
Let G be a graph. Then the treewidth of G is equal to the
maximum treewidth of the connected components of G.
Treewidth
Treewidth: Generalizing Trees
Basic Properties
Observation (2)
Let A and B be 2 graphs and let G be the disjoint union of A
and B. Then tw(G) = max{tw(A), tw(B)}.
Corollary (1)
Let G be a graph. Then the treewidth of G is equal to the
maximum treewidth of the connected components of G.
Treewidth
Treewidth: Generalizing Trees
Basic Properties
Observation (3)
If G is a forest and contains at least one edge then tw(G) = 1.
Proof:
Because of Observation (0) it holds that tw(G) ≥ 1.
Furthermore, it follows from Corollary (1) that we only need to
consider the treewidth of G’s connected components, i.e., we
need to show that every tree has a tree decomposition of width
1. Suppose that G is a tree. W.l.o.g. we can assume that G is
rooted in some arbitrary vertex and that p(t) denotes the parent
of a vertex t ∈ V(G). Then (G, X) such that X(t) := {t, p(t)} is
a tree decomposition of G of width at most 1.
Treewidth
Treewidth: Generalizing Trees
Small Tree Decompostions
Definition
A tree decomposition (T, X) is small if X(t) X(t ) for every
distinct t, t ∈ V(T).
Proposition (1)
Given a tree decomposition of a graph G. Then in polynomial
time we can construct a small tree decompositon of G (of the
same width).
Proposition (2)
Let (X, T) be a small tree decomposition of G. Then
|V(T)| ≤ |V(G)|.
Treewidth
Treewidth: Generalizing Trees
Small Tree Decompostions
Proposition (1)
Given a tree decomposition of a graph G. Then in polynomial
time we can construct a small tree decompositon of G.
Proof:
Let (T, X) be a tree decomposition of G with X(t) ⊆ X(t ) for
some distinct t, t ∈ V(T). By considering the unique path from
t to t in T we can find adjacent nodes with this property.
Hence, w.l.o.g. we can assume that {t, t } ∈ E(T).
Consequently, contracting the edge {t, t } into a new node t
and setting X(t ) := X(t ) gives a smaller tree decomposition of
G. Hence, we can continue this process until a small tree
decomposition of G is obtained.
Treewidth
Treewidth: Generalizing Trees
Small Tree Decompostions
Proposition (2)
Let (X, T) be a small tree decomposition of G. Then
|V(T)| ≤ |V(G)|.
Proof:
By induction over n = |V(G)|. If n = 1 then |V(T)| = 1, as
required.
If n > 1 then consider a leaf l of T with neighbor l . Deleting l
from T yields a small tree decomposition (T , X ) of
G := G \ (X(l) \ X(l )).
Because X(l) \ X(l ) = ∅ we obtain by induction:
|V(T)| = |V(T )| + 1 ≤ |V(G )| + 1 ≤ |V(G)|
, as required.
Treewidth
Treewidth: Generalizing Trees
Minors
Observation (4)
Let H be obtained from G by contracting an edge {v, w} into z.
Then tw(H) ≤ tw(G).
Proof:
Let (T, X) be a tree decomposition of G. Then (T, X ) such that
X(t) := X(t) ∪ {z} for every t ∈ V(T) with {v, w} ∩ X(t) = ∅
and X(t) := X(t), otherwise, is a tree decomposition of H
whose width is at most the width of (T, X).
Treewidth
Treewidth: Generalizing Trees
Minors
Definition
A graph H is a minor of a graph G if H can be obtained from a
subgraph of G via edge contractions.
Because of Observation (1) and (4) we obtain:
Observation (5)
Let H be a minor of G. Then tw(H) ≤ tw(G).
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Definitions
Let (T, X) be a tree decomposition, {t, t } ∈ E(T), and
U ⊆ V(T). We denote by Tt and Tt the 2 components of
T − {t, t } (such that Tt contains t and Tt contains t ).
Furthermore, we denote by X(U) the set of vertices
t∈U X(t).
Let G be a connected graph and S, T ⊆ V(G) be disjoint
and non-empty vertex sets of G. A set C ⊆ V(G) is a cut if
G \ C is disconnected. It is a k-cut if |C| ≤ k. Furthermore,
C is an (S, T)-cut or a cut separating S and T if G \ C
contains no paths with end vertices in both S and T.
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma
Let (T, X) be a tree decomposition of a graph G and
{t, t } ∈ E(T). Furthermore, let C := X(t) ∩ X(t ),
St := X(Tt ) \ X(Tt ) and St := X(Tt ) \ X(Tt ). Then C is an
(St , St )-cut in G.
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma
Let (T, X) be a tree decomposition of a graph G and
{t, t } ∈ E(T). Furthermore, let C := X(t) ∩ X(t ),
St := X(Tt ) \ X(Tt ) and St := X(Tt ) \ X(Tt ). Then C is an
(St , St )-cut in G.
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma
Let (T, X) be a tree decomposition of a graph G and
{t, t } ∈ E(T). Furthermore, let C := X(t) ∩ X(t ),
St := X(Tt ) \ X(Tt ) and St := X(Tt ) \ X(Tt ). Then C is an
(St , St )-cut in G.
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma
Let (T, X) be a tree decomposition of a graph G and
{t, t } ∈ E(T). Furthermore, let C := X(t) ∩ X(t ),
St := X(Tt ) \ X(Tt ) and St := X(Tt ) \ X(Tt ). Then C is an
(St , St )-cut in G.
e f g h
b
c d
a c, d, f
b, c, f
a, b, c b, e, f
d, f, g
g, h
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma
Let (T, X) be a tree decomposition of a graph G and
{t, t } ∈ E(T). Furthermore, let C := X(t) ∩ X(t ),
St := X(Tt ) \ X(Tt ) and St := X(Tt ) \ X(Tt ). Then C is an
(St , St )-cut in G.
Proof:
Because of Property T2 of a tree decomposition we obtain
C = X(t) ∩ X(t ) = X(Tt ) ∩ X(Tt ).
Hence, {St , C, St } is a partition of V(G). It hence suffices to
show that G \ C contains no edge {u, v} with u ∈ St and
v ∈ St .
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma (1)
Let (T, X) be a tree decomposition of a graph G and
{t, t } ∈ E(T). Furthermore, let C := X(t) ∩ X(t ),
St := X(Tt ) \ X(Tt ) and St := X(Tt ) \ X(Tt ). Then C is an
(St , St )-cut in G.
Proof, continued:
Let {u, v} ∈ E(G). Because of Property T1 of a tree
decomposition we know that there is a t ∈ V(T) such that
{u, v} ⊆ X(t ).
If t ∈ V(Tt ) then u, v ∈ X(Tt ) and hence u, v /∈ X(Tt ). If
t ∈ V(Tt ) then u, v ∈ X(Tt ) and hence u, v /∈ X(Tt ).
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Lemma (2)
Let G be a connected graph with tw(G) ≤ k. Then
|V(G)| = k + 1 or G has a k-cut.
Proof:
Consider a small tree decomposition (T, X) of G of width at
most k. If |V(G)| > k + 1, then |V(T)| ≥ 2, so we may consider
any two adjacent nodes t, t ∈ V(T). Because (T, X) is small it
holds that X(t) \ X(t ) = ∅ and X(t ) \ X(t) = ∅, and
|X(t) ∩ X(t )| ≤ k. Then, by the previous lemma,
C = X(t) ∩ X(t ) is a k-cut in G.
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
As an immediate consequence of Lemma (2) we obtain:
Corollary
If tw(G) = 1, then G is a forest.
Corollary
Let Kn be the complete graph on n vertices. Then
tw(Kn) = n − 1.
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
A k × l-grid, denoted Gk×l, is the
graph with vertex set:
{ (i, j) : 1 ≤ i ≤ k and 1 ≤ j ≤ l }
and edge set:
{ {(i, j), (i, j + 1)} : 1 ≤ i ≤ k, 1 ≤ j <
l }∪
{ {(i, j), (i + 1, j) : 1 ≤ i < k, 1 ≤ j ≤ l }
Treewidth
Treewidth: Generalizing Trees
Tree Decompositions and Cuts
Proposition
tw(Gk×l) ≤ min{k, l}.
As an immediate consequence of Lemma (2) we obtain:
Proposition
tw(Gk×l) ≥ min{k, l}.
Treewidth
Computing Treewidth
Outline
1 Treewidth
Dynamic Programming on Trees
Treewidth: Generalizing Trees
Computing Treewidth
Treewidth
Computing Treewidth
Computing Treewidth
The following problem is NP-hard:
k-TREEWIDTH Parameter: k
Input: A graph G and a natural number k.
Question: Is tw(G) ≤ k (and if so compute a tree
decomposition of width at most k)
Theorem
k-TREEWIDTH is fixed-parameter tractable, i.e., there are 2
FPT-algorithms for k-TREEWIDTH: (1) O(2O(k3)|V(G)|) and (2)
O(33k k(|V(G)|)2).
Theorem
Treewidth can be approximated to within k log k.
Treewidth
Computing Treewidth
Computing Treewidth
Remark
Because k-TREEWIDTH is fixed-parameter tractable we can
always assume that we are given a tree decomposition of
optimal width when designing fixed-parameter algorithms for
problems parameterized by treewidth.