Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Treewidth
Dynamic Programming on Tree Decompositions
Outline
1 Treewidth
Dynamic Programming on Tree Decompositions
Courcelle’s Theorems
Treewidth Reduction Algorithms
Treewidth
Dynamic Programming on Tree Decompositions
Some Notation
Let (T, X) be a tree decomposition of a graph G. In the
following we will assume that T is rooted in some arbitrary node
r and hence parent and child relationships between nodes in T
are well defined. We will also use the following notations. Let
t ∈ V(T), U ⊆ V(T):
T(t) denotes the subtree of T rooted at t;
X(U) denotes the set t∈U X(t);
V(t) denotes the set X(V(T(t)));
G(t) denotes the graph G[V(t)].
Treewidth
Dynamic Programming on Tree Decompositions
Nice Tree Decompositions
Definition
A tree decomposition (T, X) is nice if X(r) = ∅ and every node
t ∈ V(T) has one of the following 4 types:
Leaf Node: no children and |X(t)| = 1;
Introduce Node: 1 child t and X(t) = X(t ) ∪ {v} for
some v ∈ V(G);
Forget Node: 1 child t and X(t) = X(t ) \ {v} for some
v ∈ V(G);
Join Node: 2 children t1 and t2, and X(t) = X(t1) = X(t2);
Treewidth
Dynamic Programming on Tree Decompositions
Nice Tree Decompositions
Due to their restricted structure nice tree decomposition make
the design of dynamic programming algorithms much easier.
Furthermore, as the following Proposition shows, the overhead
to obtain a nice tree decomposition from a tree decomposition
is neglectable.
Proposition (NT)
A tree decomposition of width w and n nodes can be turned
into a nice tree decomposition of width w and O(wn) nodes in
time O(w2n).
Treewidth
Dynamic Programming on Tree Decompositions
The General Approach
The general approach to design bottom-up dynamic
programming algorithms is the following:
(1) Find out what is the essential information that we need to
know about partial solutions of the problem.
(2) Design the records to store that information.
(3) Can we obtain the solution for the problem from the set of
records stored at the root of the tree decompositon?
(4) Can we efficiently compute the records for every of the four
types of nodes of a nice tree decomposition?
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Recall:
The PARTY PROBLEM is the problem to find a maximum
weighted independent set of a vertex-weighted graph. We have
seen that it can be solved on trees in polynomial time.
We will show next how the dynamic programming approach
used to solved the PARTY PROBLEM on trees can be
generalized to graphs of bounded treewidth.
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
w-PARTY PROBLEM Parameter: w
Input: A graph vertex-weighted graph G, a natural number w
and a nice tree decomposition (T, X) of G of width at most w.
Question: Compute a the weight of a maximum weight
independent set of G.
We will show the following:
Theorem
w-PARTY PROBLEM can be solved in time O(2w w2|V(G)|) and
hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
As for trees we will use a dynamic programming bottom-up
approach that computes sets of records for each node of the
tree decomposition.
Let (T, X) be a nice tree decomposition of a vertex-weighted
graph G (with weight function w) and let t ∈ V(T). This time a
record is a pair (I, w) where I ⊆ X(t) and w is a real value.
The semantics of a record is as follows:
(I, w) ∈ R(t) iff w is the maximum weight of any independent
set S of G(t) such that S ∩ X(t) = I.
Clearly, the solution for the PARTY PROBLEM can be easily
obtained from R(r) as the real number w such that
(∅, w) ∈ R(r).
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { (∅, 0), (X(t), w(v)) }.
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t )
R(t) := { (S ∪ {v}, w + w(v)) : (S, w) ∈ R(t ) and
S ∪ {v} is an independent set ofG[X(t)] }∪
R(t )
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { (S, max{w1, w2}) : S ∩ {v} = ∅ and
(S, w1) ∈ R(t ) and
(S ∪ {v}, w2) ∈ R(t ) }
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is a join node with children t1 and t2
R(t) := { (S, w1 + w2 − w(S)) : (S, w1) ∈ R(t1) and
(S, w2) ∈ R(t2) }
Treewidth
Dynamic Programming on Tree Decompositions
Run-Time Analysis
Given a nice tree decomposition (T, X) of G the total time
required by the above dynamic programming algorithm to solve
the PARTY PROBLEM is the number of nodes of T times the
maximum time spend on any of the four types of nodes of
(T, X).
Because of Proposition (NT) the number of nodes of (T, X) is
at most tw(G)|V(G)|.
Question
What is the maximum time spend on any of the four types of
nodes of the nice tree decomposition?
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { (∅, 0), (X(t), w(v)) }.
We spend constant time at a leaf node!
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t )
R(t) := { (S ∪ {v}, w + w(v)) : (S, w) ∈ R(t ) and
S ∪ {v} is an independent set ofG } ∪ R(t )
Because we have to go over all of the at most 2w records in
R(t ) and for each record we need time O(w) to check whether
we again obtain an independent set the total time spend on an
introduce node is O(2w w).
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { (S, max{w1, w2}) : S ∩ {v} = ∅ and
(S, w1) ∈ R(t ) and
(S ∪ {v}, w2) ∈ R(t ) }
Because we have to go over all of the at most 2w records in
R(t ) and for each record we need only constant time the total
time spend on a forget node is O(2w ).
Treewidth
Dynamic Programming on Tree Decompositions
The PARTY PROBLEM on Treewidth
Let (T, X) be a nice tree decomposition of a vertex weighted
graph G with weight function w and let t ∈ V(T).
t is a join node with children t1 and t2
R(t) := { (S, w1 + w2 − w(S)) : (S, w1) ∈ R(t1) and
(S, w2) ∈ R(t2) }
Using appropiate data structures to store the records, e.g.,
hastables, the total time required for a join node is O(2w ).
Treewidth
Dynamic Programming on Tree Decompositions
Run-Time Analysis
Question
What is the maximum time spend on any of the four types of
nodes of the nice tree decomposition?
Answer
O(2w w).
Theorem
Given a nice tree decomposition (T, X) of a graph G the PARTY
PROBLEM can be solved in time O(2w w2|V(G)|).
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
w-3-COLORING Parameter: w
Input: A graph G, a natural number w and a nice tree
decomposition (T, X) of G of width at most w.
Question: Does G have a vertex coloring with at most 3
colors?
We will show the following:
Theorem
w-3-COLORING can be solved in time O(3w w2|V(G)|) and
hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T). This time a record is a 3-vertex coloring
c : X(t) → {1, 2, 3} of X(t).
The semantics of a record is as follows:
c ∈ R(t) iff c is a 3-vertex coloring of the vertices in X(t) that
can be extended to a valid 3-vertex coloring of G(t).
Clearly, the solution for the w-3-COLORING problem can be
easily obtained from R(r) by checking wether R(r) = ∅.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { c : c(v) ∈ {1, 2, 3} }.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { c : c(v) ∈ {1, 2, 3} }.
We spend constant time at a leaf node!
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t )
R(t) := { c : X(t) → {1, 2, 3} : c[X(t )] ∈ R(t ) and
c(v) = c(w) for every w ∈ NG[X(t)](v) }
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t )
R(t) := { c : X(t) → {1, 2, 3} : c[X(t )] ∈ R(t ) and
c(v) = c(w) for every w ∈ NG[X(t)](v) }
Because we have to go over all of the at most 3w records in
R(t ) and for each record we need time O(w) to obtain the
possible colors for the vertex v the total time spend on an
introduce node is O(3w w).
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { c[X(t)] : c ∈ R(t ) }
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { c[X(t)] : c ∈ R(t ) }
Because we have to go over all of the at most 3w records in
R(t ) the total time spend on a forget node is O(3w ).
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for 3-COLORING
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a join node with children t1 and t2
R(t) := R(t) ∩ R(t )
Using appropriate data structures to store the records, e.g.,
hastables, the total time required for a join node is O(3w ).
Treewidth
Dynamic Programming on Tree Decompositions
Run-Time Analysis
Because the maximum time spend at any of the four types of
the nice tree decomposition is O(3w w) we obtain:
Theorem
w-3-COLORING can be solved in time O(3w w2|V(G)|) and
hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-k-COLORING
w-k-COLORING Parameter: w
Input: A graph G, a natural number w and a nice tree
decomposition (T, X) of G of width at most w.
Question: Does G have a vertex coloring with at most k
colors?
By generalizing the above algorithm for w-3-COLORING to
w-k-COLORING in the natural way, we obtain:
Theorem
w-k-COLORING can be solved in time O(kw w2|V(G)|) and
hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-k-COLORING
Theorem
w-k-COLORING can be solved in time O(kw w2|V(G)|) and
hence is fixed-parameter tractable.
Question
The above algorithm only works for the k-COLORING, i.e., if k is
fixed and not part of the input. Can we solve the more general
w-COLORING problem?
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-COLORING
w-COLORING Parameter: w
Input: A graph G, 2 natural numbers w and k, and a nice tree
decomposition (T, X) of G of width at most w.
Question: Does G have a vertex coloring with at most k
colors?
Proposition
Let G be a graph of treewidth at most w. Then G can be
colored with at most w + 1 colors.
Corollary
w-COLORING can be solved in time O(ww w2|V(G)|) and
hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-COLORING
Proposition
Let G be a graph of treewidth at most w. Then G can be
colored with at most w + 1 colors.
Proof:
We first show that every graph G with tw(G) ≤ w has a vertex
of degree at most w. Hence, let (T, X) be a small tree
decomposition of G of width at most k and let l ∈ V(T) be a
leaf of T. Because (T, X) is small there is a v ∈ X(l) that only
occurs in l. Hence, using Property T1 we obtain that all
neighbors of v in G must be contained in X(l). Hence, v has
degree at most w in G.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-COLORING
Proposition
Let G be a graph of treewidth at most w. Then G can be
colored with at most w + 1 colors.
Proof, continued:
Using this fact and the fact that treewidth is closed under taking
subgraphs we obtain that every graph of treewidth at most w is
w-degenerate and hence can be colored by a simple greedy
algorithm with at most w + 1 colors.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
w-HAMILTONIAN CYCLE Parameter: w
Input: A graph G, a natural number w and a nice tree
decomposition (T, X) of G of width at most w.
Question: Does G have a hamiltonian cycle?
We will show the following:
Theorem
w-HAMILTONIAN CYCLE can be solved in time
O((2w ww/2)2w3|V(G)|) and hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T). This time a record is a pair (U, R) where U ⊆ X(t)
and R ⊆ [X(t) \ U]2.
The semantics of a record is as follows:
(U, R) ∈ R(t) iff the graph either U = X(t) and G(t) has a
hamiltonian cycle or (G(t) \ X(t)) ∪ (U ∪ r∈R r) has a partition
P := {P1, . . . , Pl} into paths such that:
the endpoints of each path Pi are in X(t);
U consists of all vertices in X(t) that have degree 2 with
respect to P;
P contains a path between 2 vertices u, v ∈ X(t) iff
{u, v} ∈ R.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
(U, R) ∈ R(t) iff the graph either U = X(t) and G(t) has a
hamiltonian cycle or (G(t) \ X(t)) ∪ (U ∪ r∈R r) has a partition
P := {P1, . . . , Pl} into paths such that:
the endpoints of each path Pi are in X(t);
U consists of all vertices in X(t) that have degree 2 with
respect to P;
P contains a path between 2 vertices u, v ∈ X(t) iff
{u, v} ∈ R.
Clearly, the solution for the w-HAMILTONIAN CYCLE problem
can be easily obtained from R(r) by checking wether R(r) = ∅.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
(U, R) ∈ R(t) iff the graph either U = X(t) and G(t) has a
hamiltonian cycle or (G(t) \ X(t)) ∪ (U ∪ r∈R r) has a partition
P := {P1, . . . , Pl} into paths such that:
the endpoints of each path Pi are in X(t);
U consists of all vertices in X(t) that have degree 2 with
respect to P;
P contains a path between 2 vertices u, v ∈ X(t) iff
{u, v} ∈ R.
Clearly, the solution for the w-HAMILTONIAN CYCLE problem
can be easily obtained from R(r) by checking wether R(r) = ∅.
In the following we denote by V(R) the set r∈R r!
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { (∅, ∅) }.
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a leaf node with X(t) = {v}
R(t) := { (∅, ∅) }.
We spend constant time at a leaf node!
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t )
The R(t) consists of the following sets:
R(t ), i.e., v has degree 0;
{ (U, R ∪ {n, v}) : (U, R) ∈ R(t ) ∧ n ∈ NG[X(t)](v) ∧ n /∈
U ∪ V(R) }, i.e., v has degree 1 and is connected to a
previously isolated vertex;
{ (U ∪ {n}, (R \ {u, n}) ∪ {u, v}) : (U, R) ∈ R(t ) ∧ n ∈
NG[X(t)](v) ∧ {u, n} ∈ R }, i.e., v has degree 1 and is
connected to a previous endpoint;
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t ), cont.
The R(t) consists of the following sets:
{ (U ∪ {v}, R ∪ {n1, n2}) : (U, R) ∈ R(t ) ∧ n1, n2 ∈
NG[X(t)](v) ∧ n1, n2 /∈ U ∪ V(R) }, i.e., v has degree 2 and
is connected to 2 previously isolated vertices;
{ (U ∪ {v, n1}, (R \ {{u, n1}}) ∪ {n2, u}) : (U, R) ∈
R(t ) ∧ n1, n2 ∈ NG[X(t)](v) ∧ {n1, u} ∈ R ∧ n2 /∈ U ∪ V(R) },
i.e., v has degree 2 and is connected to 1 previous
endpoint and 1 previously isolated vertex;
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t ), cont.
The R(t) consists of the following sets:
{ (U ∪ {v, n1, n2}, (R \ {{u1, n1}, {u2, n2}}) ∪
{u1, u2}) : (U, R) ∈ R(t ) ∧ n1, n2 ∈
NG[X(t)](v) ∧ {u1, n1}, {u2, n2} ∈ R }, i.e., v has degree 2
and is connected to 2 previous endpoints from different
paths;
{ (U ∪ {v, n1, n2}, ∅) : (U, R) ∈ R(t ) ∧ n1, n2 ∈
NG[X(t)](v) ∧ {n1, n2} ∈ R ∧ U = X(t ) \ {n1, n2} }, i.e., v
has degree 2 and is connected to 2 previous endpoints
from the same path (in this case we get a hamilton cyle for
G(t));
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is an introduce node with child t and {v} = X(t) \ X(t ), cont.
Can be computed in time O(w2|R(t )|).
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { (U \ {v}, R) : (U, R) ∈ R(t ) and v ∈ U }
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a forget node with child t and {v} = X(t ) \ X(t)
R(t) := { (U \ {v}, R) : (U, R) ∈ R(t ) and v ∈ U }
Can be computed in time O(|R(t )|).
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a join node with children t1 and t2
R(t) := { (U, R) :
(U1, R1) ∈ R(t1) and (U2, R2) ∈ R(t2)
U1 ∩ U2 = R1 ∩ R2 = ∅ and
R := { {u, v} : the graph P = ((X(t), R1 ∪ R2) has a
path from u to v and u and v have degree 1 in P }
U = U1 ∪ U2 ∪ { u : ∃u ,u {{u, u }, {u, u }} ⊆ R1 ∪ R2 }
}
Treewidth
Dynamic Programming on Tree Decompositions
An Algorithm for w-HAMILTONIAN CYCLE
Let (T, X) be a nice tree decomposition of a graph G and let
t ∈ V(T).
t is a join node with children t1 and t2
R(t) := { (U, R) :
(U1, R1) ∈ R(t1) and (U2, R2) ∈ R(t2)
U1 ∩ U2 = R1 ∩ R2 = ∅ and
R := { {u, v} : the graph P = ((X(t), R1 ∪ R2) has a
path from u to v and u and v have degree 1 in P }
U = U1 ∪ U2 ∪ { u : ∃u ,u {{u, u }, {u, u }} ⊆ R1 ∪ R2 }
}
Can be computed in time O(w2|R(t1)||R(t2)|).
Treewidth
Dynamic Programming on Tree Decompositions
Run-Time Analysis
It follows that the maximum time spend at any of the four types
of the nice is O(w2|R(t)|2).
Question
What is the maximum number of records?
Treewidth
Dynamic Programming on Tree Decompositions
Run-Time Analysis
|R(t)| ≤ 2w+1M, where M is the number of possible
matchings of X(t);
An easy upper bound for M is (w + 2)!, which corresponds
(assymtotically) to 2π(w + 2)(w+2
e )w+2 = O(
√
w(w)w )
using Stirling’s formula;
A better upper bound can be obtained by realizing that M
is equal to the (w + 1)-th involution number1, giving us
(w+1
e )(w+1)/2 e
√
w+1
(4e)1/4 = O(ww/2e
√
w );
Hence, |R(t)| is at most O(2w ww/2).
1
en.wikipedia.org/wiki/Telephone_number_(mathematics)
Treewidth
Dynamic Programming on Tree Decompositions
Run-Time Analysis
It follows that the maximum time spend at any of the four types
of the nice is O(w2|R(t)|2) = O(w2(2w ww/2)2).
Theorem
w-HAMILTONIAN CYCLE can be solved in time
O((2w ww/2)2w3|V(G)|) and hence is fixed-parameter tractable.
Treewidth
Dynamic Programming on Tree Decompositions
Summary: Algorithms on Treewidth
The majority of NP-hard problems can be solved in
polynomial time on graphs of bounded treewidth!
Using nice tree decompositions helps a lot, at almost no
cost.
The main challenge is finding out which information to
store for tree nodes; when this is done, proving formulas
for forget, introduce and join nodes is tedious but mostly
straightforward.
Another research subject is finding faster dynamic
programming strategies: sometime it may be possible to
store and compute fewer combinations.
Treewidth
Courcelle’s Theorems
Outline
1 Treewidth
Dynamic Programming on Tree Decompositions
Courcelle’s Theorems
Treewidth Reduction Algorithms
Treewidth
Courcelle’s Theorems
Courcelle’s Theorems
Theorem (Decision)
Let Φ be a MSOL formula of lenght k and G be a (directed)
graph on n vertices with tw(G) ≤ w. Then in time f(k, w)O(n) it
can be decided whether G satisfies Φ.
Theorem (Optimization)
Let Φ(S) be a MSOL formula of lenght k, G be a (directed)
graph on n vertices with tw(G) ≤ w, and let m be a natural
number. Then in time f(k, w)O(n) it can be decided whether
there exists an S for G with |S| ≤ m (resp. |S| ≥ m) that
satisfies Φ(S).
Treewidth
Courcelle’s Theorems
A Graph as a Relational Structure
An (undirected) graph G can be represented by a relational
structure as follows:
U = V(G) ∪ E(G) (The universe);
Vx is a unary relation on U that is satisfied if x ∈ V(G);
Ex is a unary relation on U that is satisfied if x ∈ E(G);
Ixy is a binary relation on U that is satisfied if x ∈ V(G),
y ∈ E(G), and x ∈ y.
Unary relations are also called sets and instead of Vx we also
write x ∈ V.
Treewidth
Courcelle’s Theorems
A Digraph as a Relational Structure
A directed graph G can be represented by a relational structure
as follows:
U = V(G) ∪ E(G) (The universe);
Vx is a unary relation on U that is satisfied if x ∈ V(G);
Ex is a unary relation on U that is satisfied if x ∈ E(G);
I−xy (I+xy) is a binary relation on U that is satisfied if
x ∈ V(G), y ∈ E(G), and y = (x, z) (y = (z, x)) for some
z ∈ V.
Treewidth
Courcelle’s Theorems
Monadic Second Order Logic
Monadic Second Order Logic has the following form:
An infinite set of variables (lower case letters) and relation
symbols (upper case letters) is given.
Atoms are of the form x = y for 2 variables x and y, or
Rx1 . . . xk for a k-ary relation R.
These are combined into syntactically correct logical formulas
using:
The logical connectives ¬, ∨, and ∧;
Universal and existential quantification over variables ∀x
and ∃x;
Universal and existential quantification over unary relations
(sets) ∀S and ∃S.
We also use → and ↔ as logical connectives.
Treewidth
Courcelle’s Theorems
Monadic Second Order Logic
A variable x or a relation S that is not in the scope of a
quantifier binding x or S is called free. We use the
convention Φ(x1, . . . , xk , S1, . . . , Sl) to denote that
x1, . . . , xk are free variables in Φ and S1, . . . , Sl are free
relation symbols.
Because we will apply these formulas to graphs (and
digraphs) and view V, E, and I as constants instead of free
set variables, the above formula will be called Φ instead of
Φ(V, E, I).
We employ the usual semantic interpretation of MSOL
formulas, e.g., Φ ∧ φ is satisfied iff both Φ and φ are
satisfied, and ∀xφ(x) is satisfied if for all values of the
variable x, φ(x) is satisfied.
Treewidth
Courcelle’s Theorems
Example
G is bipartite
Φ(V, E, I) := ∃S∃T((∀x(Vx → (Sx ∨ Tx)))∧
∀x∀y((¬(x = y) ∧ ∃z(Ixz ∧ Iyz)) → ¬((Sx ∧ Sy) ∨ (Tx ∧ Ty))))
Treewidth
Courcelle’s Theorems
Simplifying the notations
The example formula expressed a very simple property but was
already hard to read. Therefore, in addition to →, we introduce
some more macros and standard formulas that will often be
used:
S ⊆ T stands for ∀x(Sx → Tx);
∀x ∈ S φ(x) stands for ∀x(Sx → φ(x)), and ∃x ∈ S is
defined analogously;
∀S ⊆ T φ(S) stands for ∀S((∀x ∈ STx) → φ(S)), and
∃S ⊆ T is defined analogously;
adjV (x, y) stands for ¬(x = y) ∧ ∃e ∈ E(Ixe ∧ Iye);
adjE (e, f) stands for ¬(e = f) ∧ ∃x ∈ V(Ixe ∧ Ixf);
∀xy ∈ E φ(x, y) stands for
∀x ∈ V ∀y ∈ V adjV (x, y) → φ(x, y).
Treewidth
Courcelle’s Theorems
More examples
S is a vertex cover
VC(S) := S ⊆ V ∧ ∀e ∈ E ∃s ∈ S Ise
S is a dominating set
DS(S) := S ⊆ V ∧ ∀v ∈ V ∃s ∈ S adjV (v, s)
Treewidth
Courcelle’s Theorems
More examples
G is 3-vertex colorable
Col3 := ∃X1 ⊆ V ∃X2 ⊆ V ∃X3 ⊆ V
(∀x ∈ V ((X1x ∨ X2x ∨ X3x)∧
¬(X1x ∧ X2x) ∧ ¬(X1x ∧ X3x) ∧ ¬(X2x ∧ X3x))∧
∀xy ∈ E(¬(X1x ∧ X1y) ∧ ¬(X2x ∧ X2y) ∧ ¬(X3x ∧ X3y)))
Clearly, k-vertex colorability can be expressed this way for any
k (Colk ). However, the formula has length O(k2).
Treewidth
Courcelle’s Theorems
Some More Macros
∃≥2x φ(x) stands for ∃x∃y φ(x) ∧ φ(y) ∧ ¬(x = y), and
∃≥k xφ(x) is defined analogously (observe that the formula
length grows with k).
∃=k x φ(x) stands for ∃≥k x φ(x) ∧ ¬∃≥k+1x φ(x).
S = ∅ stands for ¬∃xSx.
∃S V stands for ∃S ⊆ V ∧ ∃xVx ∧ ¬Sx, and ∀S V is
defined analogously.
Treewidth
Courcelle’s Theorems
Some More Examples
The set T of edges induces a connected and spanning
subgraph
CS(T) :=
T ⊆ E ∧ ∀S V(¬S = ∅ → ∃xy ∈ T(Sx ∧ ¬Sy))
G contains a hamiltonian cycle
HC :=
∃T ⊆ E(CS(T) ∧ ∀x ∈ V∃=2e ∈ T Ixe)
Treewidth
Courcelle’s Theorems
An Example for Digraphs
C induces a set of vertex disjoint (directed) cycles
DC(C) := C ⊆ E∧
∀x ∈ V(∃e ∈ C(I+xe ∨ I−xe) → (∃=1e ∈ C I+xe ∧ ∃=1e ∈
C I−xe))
S is a (directed) feedback vertex set
DFVS(S) := S ⊆ V∧
∀C ⊆ A (DC(C) → ∃x ∈ S ∃e ∈ CI+xe)
Treewidth
Courcelle’s Theorems
Algorithms for treewidth: Summary
Many (di)graph problems can be solved in linear time for
graphs of bounded treewidth. This includes (almost) all
problems treated in this lecture series.
More precisely, there are FPT algorithms for the general
problems parameterized by tree width. (Since an FPT
algorithm for deciding tree width exists, we may be sloppy
here.)
For designing an algorithm, dynamic programming is
necessary. To decide whether such an algorithm exists,
monadic second order logic is a strong tool.
Treewidth
Treewidth Reduction Algorithms
Outline
1 Treewidth
Dynamic Programming on Tree Decompositions
Courcelle’s Theorems
Treewidth Reduction Algorithms
Treewidth
Treewidth Reduction Algorithms
Introduction
So far the use of treewidth has be restricted to bounded
treewidth graphs. However, as we will see, by using structural
properties about a problem, treewidth reduction algorithms can
be applied even to instances with unbounded treewidth.
Treewidth
Treewidth Reduction Algorithms
Example: Vertex Cover
Proposition (1)
k-VERTEX COVER can be solved in linear time on graphs of
bounded treewidth (Because of Courcelle’s Theorem).
Propostion (2)
Let I := (G, k) be an instance of k-VERTEX COVER such that
tw(G) > k. Then I is a NO instance.
Treewidth
Treewidth Reduction Algorithms
Example: Vertex Cover
Using Proposition (1) and (2) we obtain the following algorithm
to solve an instance I := (G, k) of k-VERTEX COVER:
Decide whether tw(G) ≤ k and if so compute a tree
decomposition T = (T, X) of G of width at most k.
If tw(G) ≤ k, then use the tree decomposition T of G to
decide I (Proposition (1)).
If tw(G) > k return NO.
Treewidth
Treewidth Reduction Algorithms
Example: Vertex Cover
Using Proposition (1) and (2) we obtain the following algorithm
to solve an instance I := (G, k) of k-VERTEX COVER:
Decide whether tw(G) ≤ k and if so compute a tree
decomposition T = (T, X) of G of width at most k.
Running time O(f(k)|V(G)|)
If tw(G) ≤ k, then use the tree decomposition T of G to
decide I (Proposition (1)).
Running time O(g(k)|V(G)|)
If tw(G) > k return NO.
Treewidth
Treewidth Reduction Algorithms
Example: Vertex Cover
Using Proposition (1) and (2) we obtain the following algorithm
to solve an instance I := (G, k) of k-VERTEX COVER:
Decide whether tw(G) ≤ k and if so compute a tree
decomposition T = (T, X) of G of width at most k.
Running time O(f(k)|V(G)|)
If tw(G) ≤ k, then use the tree decomposition T of G to
decide I (Proposition (1)).
Running time O(g(k)|V(G)|)
If tw(G) > k return NO.
This gives an FPT algorithm for k-VERTEX COVER.
Treewidth
Treewidth Reduction Algorithms
Example: Vertex Cover
It remains to show Proposition (2):
Propostion (2)
Let I := (G, k) be an instance of k-VERTEX COVER such that
tw(G) > k. Then I is a NO instance.
Proof:
It suffices to show that if G has a k-VC C ⊆ V(G) then G has
treewidth at most k. Becaus C is a vertex cover it follows that
G \ C is an independent set and hence has treewidth 0. Thus,
let (T, X) be a tree decomposition of G \ C of width 0. Then it is
straighforward to check that (T, X ) with X := X ∪ C is a tree
decomposition of G of width at most k.
Treewidth
Treewidth Reduction Algorithms
Example: Feedback Vertex Set
k-FEEDBACK VERTEX SET Parameter: k
Input: A graph G and a natural number k.
Question: Does G have a feedback vertex set of size at most
k, i.e., is there a set S ⊆ V(G) with |S| ≤ k such that G \ S is
acyclic?
Question
Is k-FEEDBACK VERTEX SET fixed-parameter tractable?
Treewidth
Treewidth Reduction Algorithms
Example: Feedback Vertex Set
Proposition (1)
k-FEEDBACK VERTEX SET can be solved in linear time on
graphs of bounded treewidth (Because of Courcelle’s
Theorem).
Propostion (2)
Let I := (G, k) be an instance of k-FEEDBACK VERTEX SET
such that tw(G) > k + 1. Then I is a NO instance.
Treewidth
Treewidth Reduction Algorithms
Example: Feedback Vertex Set
Propostion (2)
Let I := (G, k) be an instance of k-FEEDBACK VERTEX SET
such that tw(G) > k + 1. Then I is a NO instance.
Proof:
It suffices to show that if G has a k-FVS S ⊆ V(G) then G has
treewidth at most k + 1. Because S is a feedback vertex set it
follows that G \ S is a forest and hence has treewidth at most 1.
Thus, let (T, X) be a tree decomposition of G \ S of width 1.
Then it is straighforward to check that (T, X ) with X := X ∪ S
is a tree decomposition of G of width at most k + 1.
Treewidth
Treewidth Reduction Algorithms
Example: Feedback Vertex Set
Question
Is k-FEEDBACK VERTEX SET fixed-parameter tractable?
Answer
Yes, and this time it is not as obvious as for k-VERTEX COVER.
Treewidth
Treewidth Reduction Algorithms
Example: Longest Cycle
k-LONG CYCLE Parameter: k
Input: A graph G and a natural number k.
Question: Does G have a cycle of length at least k?
The above problem is clearly NP-hard (reduction from
Hamiltonian Cycle) and not easily seen to be FPT.
Treewidth
Treewidth Reduction Algorithms
Example: Longest Cycle
Proposition (1)
k-LONG CYCLE can be solved in linear time on graphs of
bounded treewidth (Because of Courcelle’s Theorem).
Propostion (2)
Let I := (G, k) be an instance of k-LONG CYCLE such that
tw(G) ≥ k − 2. Then I is a YES instance.
Treewidth
Treewidth Reduction Algorithms
Example: Longest Cycle
Propostion (2)
Let I := (G, k) be an instance of k-LONG CYCLE such that
tw(G) ≥ k − 2. Then I is a YES instance.
Proof:
Assume to the contrary that G has no cycle of length at least k
and let T be a spanning tree of G obtained by Depth First
Search of G starting in r ∈ V(G). Because T is obtained via
Depth First Search all edges in E(G) \ E(T) are between
vertices v, w such that w is on the unique path from v to r in T
(or vice versa).
Treewidth
Treewidth Reduction Algorithms
Example: Longest Cycle
Propostion (2)
Let I := (G, k) be an instance of k-LONG CYCLE such that
tw(G) ≥ k − 2. Then I is a YES instance.
Proof, cont.:
Furthermore, because G contains no cycle of length at least k
all these vertices v and w have distance at most k − 2 in T. For
t ∈ V(T) let A(t) be the set of the first k − 2 vertices on the
unique path from t to r in T. Then (T, X) with X(t) := {t} ∪ A(t)
is a tree decomposition of G of width at most k − 2.
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
k-MAXIMUM LEAF SPANNING TREE Parameter: k
Input: A graph G and a natural number k.
Question: Does G have a spanning tree with at least k leaves?
Previous algorithm used Kernelization!
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Proposition (1)
k-MAXIMUM LEAF SPANNING TREE can be solved in linear time
on graphs of bounded treewidth (Because of Courcelle’s
Theorem).
Propostion (2)
???
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Let G be a graph with spanning tree T. We denote by L(T) the
set of leaves of T and by N3(T) the set of vertices that have at
least 1 neighbor with degree at least 3 in T.
Proposition (2A)
Let G and T be as above and let {u, v} ∈ E(G) \ E(T) where
u /∈ L(T) and v /∈ N3(T). Then there is an edge {v, w} ∈ E(T)
such that T − {v, w} + {u, v}) is a spanning tree with more
leaves than T.
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Proposition (2A)
Let G and T be as above and let {u, v} ∈ E(G) \ E(T) where
u /∈ L(T) and v /∈ N3(T). Then there is an edge {v, w} ∈ E(T)
such that (V(T), (E(T) \ {{v, w}}) ∪ {{u, v}}) is a spanning
tree with more leaves than T.
Proof:
T + {u, v} contains a unique cycle, which contains the edge
{u, v}. Let {v, w} be the other edge incident to v on that cycle.
Clearly, T + {u, v} − {v, w} is again a spanning tree. Because
v /∈ N3(T), w becomes a leaf and because u was not a leaf in
T all leaves of T remain leaves.
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Proposition (2B)
Let T be a spanning tree of G such that every edge of
E(G) \ E(T) has at least 1 end point in L(T) ∪ N3(T). Then
tw(G) ≤ |L(T) ∪ N3(T)| + 1.
Proof:
Let (T, X) be a tree decomposition of T of width 1. Then
(T, X ) with X := X ∪ L(T) ∪ N3(T) is a tree decomposition of
G of the required width.
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Proposition (2C)
For any tree T, it holds that |N3(T)| ≤ 3|L(T)| − 6
Proof:
Let H contain the vertices of degree at least 3. Then:
|N3(T)| ≤ v∈H d(v) ≤ 3 v∈H(d(v) − 2) =
3( v∈V (d(v) − 2) + |L(T)|) = 3(2|E(T)| − 2|V(T)| + |L(T)|) =
3(|L(T)| − 2)
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
An Algorithm for k-MLST
(1) Construct a spanning tree T of G
(2) While there is an edge {u, v} ∈ E(G) \ E(T) with
u /∈ L(T) and v /∈ N3(T) do
T := T + {u, v} − {v, w}
(3) If T has at least k leaves then return YES
(4) Use T to construct a tree decomposition (T, X) of
G of width at most 4k.
(5) Answer the problem using dynamic programming
over (T, X).
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Analysis of the Algorithm
Clearly, the algorithm returns the correct answer.
Because every iteration in Step (2) increases the number
of leaves (Proposition (2A)), Step (2) stops after at most
|V(G)| iterations.
Because of Propositions (2B) and (2C) the tree
decomposition of width 4k used for Step (4) can actually
be found.
Hence, all steps apart from (5) take polynomial time.
However, because of Proposition (1), Step (5) can be
executed in time f(4k)O(n).
Treewidth
Treewidth Reduction Algorithms
Example: Maximum Leaf Spanning Tree
Analysis of the Algorithm
Clearly, the algorithm returns the correct answer.
Because every iteration in Step (2) increases the number
of leaves (Proposition (2A)), Step (2) stops after at most
|V(G)| iterations.
Because of Propositions (2B) and (2C) the tree
decomposition of width 4k used for Step (4) can actually
be found.
Hence, all steps apart from (5) take polynomial time.
However, because of Proposition (1), Step (5) can be
executed in time f(4k)O(n).
The above algorithm is an FPT algorithm for k-MLST!