Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Iterative Compression
Introduction
Outline
1 Iterative Compression
Introduction
Iterative Compression
Introduction
Iterative Compression
Iterative Compression
Introduction
Motivation
an easy but surprisingly powerful trick
Most useful for deletion problems, i.e., delete k things to
achieve some property
like color coding, iterative compression comes for free;
Iterative Compression
Introduction
A Simple Example: Vertex Cover
k-VERTEX COVER Parameter: k
Input: A graph G and an integer k.
Question: Does G have a vertex cover of size at most k?
Idea: Reduce the problem to an easier compression version of
the problem.
k-VERTEX COVER COMPRESSION Parameter: k
Input: A graph G, an integer k, and a vertex cover C of size
at most k + 1.
Question: Does G have a vertex cover of size at most k?
Iterative Compression
Introduction
A Simple Example: Vertex Cover
Idea: Reduce the problem to an easier compression version of
the problem.
k-VERTEX COVER COMPRESSION Parameter: k
Input: A graph G, an integer k, and a vertex cover C of size
at most k + 1.
Question: Does G have a vertex cover of size at most k?
There are 2 questions remaining:
How to solve the compression problem?
How to reduce k-VERTEX COVER to the compression
problem?
Iterative Compression
Introduction
A Simple Example: Vertex Cover
k-VERTEX COVER COMPRESSION Parameter: k
Input: A graph G, an integer k, and a vertex cover C of size at
most k + 1.
Question: Does G have a vertex cover of size at most k?
An Algorithm for k-VERTEX COVER COMPRESSION
For every CKEEP ⊆ C do
CREM := C \ CKEEP;
If G[CREM] contains no edges then
CNEW := N[CREM] \ C;
If |CNEW| + |CKEEP| ≤ k then
return CNEW ∪ CKEEP;
return NO;
Iterative Compression
Introduction
A Simple Example: Vertex Cover
k-VERTEX COVER COMPRESSION Parameter: k
Input: A graph G, an integer k, and a vertex cover C of size at
most k + 1.
Question: Does G have a vertex cover of size at most k?
Proof of Correctness of the Algorithm (sketch):
It is straightforward to check that if the algorithm returns a set
then this set is a vertex cover of G of size at most k.
On the other hand any vertex cover C of size at most k must
contain N[C \ C ] \ C and hence if a solution exists it is found by
the algorithm!
Iterative Compression
Introduction
A Simple Example: Vertex Cover
Theorem
k-VERTEX COVER COMPRESSION can be solved in time
O(2k nO(1)).
How can we use the compression problem to solve vertex
cover?
Start with the empty graph and add vertices one by one
Iterative Compression
Introduction
A Simple Example: Vertex Cover
An Algorithm for k-VERTEX COVER
C := ∅;
V := ∅;
For every v ∈ V(G) do
V := V ∪ {v};
if C is not a vertex cover for G[V] then
C := C ∪ {v};
if |C| > k then;
if k-VCC(G[V], C, k) is a NO-instance then
return NO;
C := k-VCC(G[V], C, k);
return YES;
Iterative Compression
Introduction
A Simple Example: Vertex Cover
An Algorithm for k-VERTEX COVER
k-VERTEX COVER can be solved in time O(2k nO(1)).
Iterative Compression
Introduction
General Iterative Compression
We can use the approach for any minimization problem on
instances G that have an integer objective value and where we
can construct a sequence G1, . . . , Gn of polynomial length with
Gn = G and:
(1) A k-solution for G1 exists and can be found in polynomial
time.
(2) If Gi has a k-solution then Gi+1 has a k + 1-solution, which
can be found in polynomial time.
(3) If Gi has no k-solution then G has no k-solution.
(4) If a (k + 1)-solution S for Gi+1 is given, then there is an
FPT algorithm for parameter k that decides whether Gi+1
has a k-solution (The compression step).
Iterative Compression
Introduction
General Iterative Compression
For problems satisfying the properties of the previous slide, the
following algorithm is an FPT-algorithm for parameter k that
decides whether a k-solution exists for G:
The General Algorithm for Iterative Compression
Let S1 be a k-solution for G1;
For i = 1 to i = n − 1 do;
Use Si to construct a (k + 1)-solution Si+1 for Gi+1;
if COMP(Gi+1, Si+1, k) is a NO-instance then
return NO;
Si+1 := COMP(Gi+1, Si+1, k);
return YES;
Iterative Compression
Introduction
Example: Graph Bipartisation
k-GRAPH BIPARTISATION Parameter: k
Input: A graph G and an integer k.
Question: Is there an S ⊆ V(G) with |S| ≤ k such that G \ S is
bipartite?
Standard example for the use of iterative compression.
Very hard to tackle without iterative compression.
Iterative Compression
Introduction
Example: Graph Bipartisation
Using the sequence Gi := G[v1, . . . , vi] for an arbitrary ordering
v1, . . . , v|V(G)| of the vertices of G we obtain:
(1) S1 := ∅ is a bipartization of G1.
(2) If Si is a k-bipartization for Gi then Si+1 := Si ∪ {vi+1} is a
(k + 1)-bipartization for Gi+1.
(3) If Gi has no k-bipartization then G has no k-bipartization.
(4) FPT-algorithm for compression version????
Hence, we only need to find an FPT-algorithm for the
compression version of the problem!
Iterative Compression
Introduction
Example: Graph Bipartisation
Using the sequence Gi := G[v1, . . . , vi] for an arbitrary ordering
v1, . . . , v|V(G)| of the vertices of G we obtain:
(1) S1 := ∅ is a bipartization of G1.
(2) If Si is a k-bipartization for Gi then Si+1 := Si ∪ {vi+1} is a
(k + 1)-bipartization for Gi+1.
(3) If Gi has no k-bipartization then G has no k-bipartization.
(4) FPT-algorithm for compression version????
Hence, we only need to find an FPT-algorithm for the
compression version of the problem!
Iterative Compression
Introduction
Example: Graph Bipartisation
k-GRAPH BIPARTISATION COMPRESSION Parameter: k
Input: A graph G, an integer k, and a S ⊆ V(G) with
|S| ≤ k + 1 s.t. G \ S is bipartite.
Question: Is there an S ⊆ V(G) with |S | ≤ k such that G \ S
is bipartite?
Question
How to solve this problem?
Iterative Compression
Introduction
Example: Graph Bipartisation
Answer
Guess the intersection SKEEP of an optimal solution with S.
Then the vertices in SREM := S \ SKEEP are not part of an
optimal solution.
Guess a bipartition {A, B} of the vertices in SREM (s.t. A
and B are independent sets in G).
Then the graph G \ SKEEP has a small bipartization (that
uses no vertices from SREM) if and only if the graph G \ S
has a small bipartization where the neighbors the
neighbors of A in G and the neighbors of B in G are in
different parts of the bipartization.
Iterative Compression
Introduction
Example: Graph Bipartisation
Hence, after guessing the at most 3k partitions of S we are left
with the following problem:
k-{A, B}-GRAPH BIPARTISATION Parameter: k
Input: A bipartite graph G, an integer k, and 2 independent
vertex sets A and B.
Question: Is there a S ⊆ V(G) with |S | ≤ k such that G \ S
has a bipartization such that the vertices in A \ S and B \ S
are in different parts?
Question
How to solve this problem?
Iterative Compression
Introduction
Example: Graph Bipartisation
Answer
Find an arbitrary bipartization {A0, B0} of G.
Then the vertices in C := (A0 ∩ B) ∪ (B0 ∩ A) have to
change, while the vertices in R := (A0 ∩ A) ∪ (B0 ∩ B)
should remain in the same part.
Observation: There is a set S ⊆ V(G) such that G \ S has
the required bipartization if and only if S separates C and
R, i.e., no component of G \ S contains vertices from both
C \ S and R \ S.
Iterative Compression
Introduction
Example: Graph Bipartisation
Observation
There is a set S ⊆ V(G) such that G \ S has the required
bipartization if and only if S separates C and R, i.e., no
component of G \ S contains vertices from both C \ S and R \ S.
Proof (sketch):
→ In a bipartitation of G \ S every vertex either changed parts
or stays in the same part. Adjacent vertices have to do the
same. Hence, every component of G \ S either changed or
remained in the same part.
← Flip the parts for all vertices in components of G \ S
containing vertices from C. Hence, no vertex from R is flipped.
Iterative Compression
Introduction
Example: Graph Bipartisation
Using max-flow min-cut techniques we can check whether there
is such a set S that separates C and R in time O(k|E(G)|).
Theorem
k-GRAPH BIPARTIZATION COMPRESSION can be solved in time
O(3k nO(1)).
And using our iterative compression framework, we obtain:
Theorem
k-GRAPH BIPARTIZATION can be solved in time O(3k nO(1)).
Iterative Compression
Introduction
Example: Feedback Vertex Set
k-FEEDBACK VERTEX SET Parameter: k
Input: A graph G and an integer k.
Question: Is there a set S ⊆ V(G) with |S| ≤ k and G \ S is a
tree?
Iterative Compression
Introduction
Example: Feedback Vertex Set
Using the sequence Gi := G[v1, . . . , vi] for an arbitrary ordering
v1, . . . , v|V(G)| of the vertices of G we obtain:
(1) S1 := ∅ is a k-FVS for G1.
(2) If Si is a k-FVS for Gi then Si+1 := Si ∪ {vi+1} is a
(k + 1)-FVS for Gi+1.
(3) If Gi has no k-FVS then G has no k-FVS.
(4) FPT-algorithm for compression version????
Hence, we only need to find an FPT-algorithm for the
compression version of the problem!
Iterative Compression
Introduction
Example: Feedback Vertex Set
Using the sequence Gi := G[v1, . . . , vi] for an arbitrary ordering
v1, . . . , v|V(G)| of the vertices of G we obtain:
(1) S1 := ∅ is a k-FVS for G1.
(2) If Si is a k-FVS for Gi then Si+1 := Si ∪ {vi+1} is a
(k + 1)-FVS for Gi+1.
(3) If Gi has no k-FVS then G has no k-FVS.
(4) FPT-algorithm for compression version????
Hence, we only need to find an FPT-algorithm for the
compression version of the problem!
Iterative Compression
Introduction
Example: Feedback Vertex Set
k-FEEDBACK VERTEX SET COMPRESSION Parameter: k
Input: A graph G , an integer k, and a k + 1-FVS of G.
Question: Is there a k-FVS for G?
Question
How to solve this problem?
Iterative Compression
Introduction
Example: Feedback Vertex Set
Answer
Again we guess the intersection of S with an optimal solution.
There are 2k+1 such guesses and for each guess we have to
solve an instance of k-FEEDBACK VERTEX SET DISJOINT
defined below.
k-S-DISJOINT FEEDBACK VERTEX SET Parameter: |S|
Input: A graph G , and a FVS S of G.
Question: Is there a |S| − 1-FVS for G that is disjoint from S?
Iterative Compression
Introduction
Example: Feedback Vertex Set
k-S-DISJOINT FEEDBACK VERTEX SET Parameter: |S|
Input: A graph G , and a FVS S of G.
Question: Is there a |S| − 1-FVS for G that is disjoint from S?
Goal
We want to solve the above problem using kernelization.
Iterative Compression
Introduction
Example: Feedback Vertex Set
Degree 1 rule
If v ∈ V(G) \ S has degree 1 in G. Then G has a k-S-DFVS iff
G \ {v} has a k-S-DFVS.
Iterative Compression
Introduction
Example: Feedback Vertex Set
Degree 2 rule
If v ∈ V(G) \ S has 2 neighbors u, w in G and w /∈ S. Then
either
(1) {v, w} ∈ E(G) and G has a k-S-DFVS iff G \ {w} has a
k − 1-S-DFVS, or
(2) {v, w} /∈ E(G) and G has a k-S-DFVS iff G has a
k-S-DFVS, where G is obtained by contracting {v, w}.
Hence, in a reduced instance (G, S, k) of k-DFVS, all vertices
in V(G) \ S have degree at least 3, or only neighbors in S.
Iterative Compression
Introduction
Example: Feedback Vertex Set
Goal
Let (G, S, k) be a reduced k-S-DFVS instance and suppose a
k-S-DFVS S exists. We want to prove an upper bound on
|V(G)|.
Let T := G \ S. Then T is a forest.
Let H be the vertices in T with degree at least 3 in T.
Let L be the vertices in T with degree 1 in T.
Let R be the vertices in T with degree 2 in T.
Let Z be the vertices in T with degree 0 in T.
Let H := H ∩ S , L := L ∩ S , R := R ∩ S and Z := Z ∩ S .
Iterative Compression
Introduction
Example: Feedback Vertex Set
Because |E(T)| = 1
2 v∈V(T) dT (v), we have:
|E(T)| = 1
2 |L| + |R| + 1
2 v∈H dT (v)
Furthermore, the number of edges removed by deleting
S = H ∪ L ∪ R is at most:
|L | + 2|R | + v∈H dT (v)
Proposition
Let T be a forest with c components, where the set H (L)
contains the vertices of degree at least 3 (exactly 1),
respectively. Then v∈H(dT (v) − 2) = |L| − 2c.
Iterative Compression
Introduction
Example: Feedback Vertex Set
Combining the previous (in)equalities, we obtain:
|E(T \ S )| ≥
1
2 |L| + |R| + 1
2 v∈H dT (v) − |L | − 2|R | − v∈H dT (v) ≥
v∈H(dT (v) − 1) + |R| − |L | − 2|R | − v∈H dT (v) =
v∈H\H dT (v) − |H| + |R| − |L | − 2|R | ≥
3|H \ H | − |H| + |R| − |L | − 2|R | =
2|H| − 3|H | + |R| − 2|R | − |L |
Iterative Compression
Introduction
Example: Feedback Vertex Set
Because G is reduced the vertices in L, R, and Z have at least
2, 1, or 2 neighbors in S, respectively. Hence:
|E(G \ S )| ≥ |E(T \ S )| + 2|L \ L | + |R \ R | + 2|Z \ Z | ≥
2|H| − 3|H | + |R| − 2|R | − |L | + 2|L| − 2|L | + |R| − |R | +
2|Z| − 2|Z | =
2|H| − 3|H | + 2|R| − 3|R | + 2|L| − 3|L | + 2|Z| − 2|Z |
Because S is FVS G \ S is a forest and hence:
|E(G\S )| ≤ |V(G\S )|−1 = |S|+|H|+|L|+|R|+|Z|−|S |−1
Iterative Compression
Introduction
Example: Feedback Vertex Set
Combining these bounds gives:
2|H| − 3|H | + 2|R| − 3|R | + 2|L| − 3|L | + 2|Z| − 2|Z | ≤
|E(G \ S )| ≤
|S| + |H| + |L| + |R| + |Z| − |S | − 1 ↔
|H| + |L| + |R| + |Z| ≤ 2|S | + |S| − 1 ↔
|V(G) \ S| ≤ 3k
Hence, the reduced graph G has at most 4k + 1 vertices!
Iterative Compression
Introduction
Example: Feedback Vertex Set
Theorem
Let G be a graph that has a FVS S with |S| = k + 1. Then it can
be decided whether G has a k-S-DFVS in time
nO(1) + O∗(6.75k ).
Algorithm
(1) If G[S] contains a cycle, return NO.
(2) Apply the degree 1 and 2 reduction rules until a reduced
instance (G , S, k ) is obtained (This needs time nO(1)).
(3) If |V(G ) \ S| > 3k, return NO.
(4) test all subsets S ⊆ V(G) \ S with |S | = k . If one of them
is a FVS return YES, otherwise return NO.
Iterative Compression
Introduction
Example: Feedback Vertex Set
Algorithm
(1) If G[S] contains a cycle, return NO.
(2) Apply the degree 1 and 2 reduction rules until a reduced
instance (G , S, k ) is obtained (This needs time nO(1)).
(3) If |V(G ) \ S| > 3k, return NO.
(4) test all subsets S ⊆ V(G) \ S with |S | = k . If one of them
is a FVS return YES, otherwise return NO.
The correctness of the algorithm follows from the previous
slides. What about the complexity bound?
Iterative Compression
Introduction
Example: Feedback Vertex Set
Theorem (Stirling’s approximation)
limn→∞
n!√
2πn( n
e
)n
= 1
Corollary
n! ∈ Θ(
√
n(n
e )n)
Recall
f(n) ∈ Ω(g(n)) means: there is c and N such that for every
n > N it holds that f(n) ≥ cg(n).
f(n) ∈ Θ(g(n)) means: f(n) ∈ O(g(n)) and f(n) ∈ Ω(g(n)).
Clearly, if f1(n) ∈ Θ(g1(n)) and f2(n) ∈ Θ(g2(n)), then
f1(n)f2(n) ∈ Θ(g1(n)g2(n)) and f1(n)/f2(n) ∈ Θ(g1(n)/g2(n)).
Iterative Compression
Introduction
Example: Feedback Vertex Set
Applying the reduction rules takes time nO(1).
Let the reduced instance G have n vertices not in S. If
n ≤ 3k (and k ≥ 2), then the number of sets tested is:
n
k ≤ 3k
k ≤ 3k
k = (3k)!
(2k)!k! ∈
Θ(
√
3k(3k)3k e−3k
√
2k(2k)2k e−2k
√
kkk e−k
)) ∈
O(33k
22k ) = O(33
22 )k ) = O(6.75k )
Testing whether a set S is a FVS can be done in polynomial
time kO(1), hence the total time complexity is
nO(1) + O(6.75k )kO(1).
Iterative Compression
Introduction
Example: Feedback Vertex Set
On the last slide we had a function f(k) ∈ Θ(6.75k kc) for some
constant c.
Observe that: f(k) ∈ O((6.75 + )k ), but f(k) /∈ O(6.75k ).
So the polynomial factor kc seems irrelevant, but still we
may not just omit it using the O-notation.
To get around this annoying situation the O∗ notation is
defined less precise as the O-notation and one can state
6.75k kc ∈ O∗(6.75k ).
Iterative Compression
Introduction
Example: Feedback Vertex Set
Hence, the overall complexity for the compression problem is
nO(1) + O∗(6.75k ). Because we have to make O(2k ) guesses
to reduce to the compression problem, we obtain:
Theorem
k-FVS can be decided in time nO(1)O∗(13.5k ).