Fixed-Parameter Algorithms, IA166
Sebastian Ordyniak
Faculty of Informatics
Masaryk University Brno
Spring Semester 2013
Kernelization
Introduction
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
Introduction
Introduction/Motivation
Kernelization is a technique to obtain FPT algorithms.
Kernelization algorithms are preprocessing algorithms that
can be used to enhance any algorithmics method.
Kernelization also gives a theoretical framework for
mathematically evaluating preprocessing algorithms.
Kernelization algorithms are related to approximation
algorithms.
Kernelization
A Simple Kernel for VERTEX COVER
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
A Simple Kernel for VERTEX COVER
A Simple Kernel for VERTEX COVER
k-VERTEX COVER (k-VC) Parameter: k
Input: A graph G and a natural number k.
Question: Does G have a vertex cover S with |S| ≤ k?
Kernelization
A Simple Kernel for VERTEX COVER
Some Observations
Observation (1)
Let (G, k) be a k-VC instance and let v be an isolated vertex of
G. Then (G, k) and (G \ {v}, k) are equivalent instances of
k-VC.
Observation (2)
Let (G, k) be a k-VC instance and let v be a vertex of G with
degree greater than k. Then (G, k) and (G \ {v}, k − 1) are
equivalent instances of k-VC.
Observation (3)
Let G be a graph with maximum degree k that admits a vertex
cover with at most k vertices. Then |E(G)| ≤ k2.
Kernelization
A Simple Kernel for VERTEX COVER
The Kernel
Theorem
Let (G, k) be a k-VC instance. In polynomial time we can obtain
an equivalent k-VC instance (G , k ) with |E(G )| ≤ O(k2).
Proof:
Iteratively remove isolated vertices and vertices with degree
greater than k. By Obervations (1) and (2) the resulting
instance (G , k ) is equivalent to the original instance and
k ≤ k.
If |E(G )| > k 2 then by Observation (3) (G , k ) is a
NO-instance and we may return any trivial and small
NO-instance of k-VC. Otherwise we return (G , k ).
Kernelization
A Simple Kernel for VERTEX COVER
Remarks
Theorem
Let (G, k) be a k-VC instance. In polynomial time we can obtain
an equivalent k-VC instance (G , k ) with |E(G )| ≤ O(k2).
Remark:
The above theorem is easily extended to an FPT-algorithm:
Compute the reduced instance (G , k ) from the above
theorem. This takes only a polynomial amount of time.
Solve k-VC by brute-force on (G , k ). Because
|E(G )| ≤ k 2 ≤ k2 this takes time at most 2k2
.
Hence, the running time for the whole algorithm is O∗(2k2
).
Kernelization
A Simple Kernel for VERTEX COVER
Remarks
This preprocessing algorithm used a parameter dependent
preprocessing rule: not so nice, i.e., not immediately
applicable to non-parameterized optimization problems.
Preprocessing algorithms of this type (kernelization
algorithms) always give FPT-algorithms with nice additive
complexities.
Kernelization
Kernelization: Definition, Basic Facts, and Motivation
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
Kernelization: Definition, Basic Facts, and Motivation
Definition
Definition
A kernelization algorithm A for a parameterized problem (Q, κ)
is a polynomial time algorithm that for every instance X of
(Q, κ) returns an equivalent instance X with |X | ≤ f(κ(X)) for
some arbitrary but computable function f : N → N.
This is also called an f(κ)-kernel for (Q, κ).
Remark
Usually, κ(X ) ≤ κ(X). This property is sometimes added to the
definition.
Kernelization
Kernelization: Definition, Basic Facts, and Motivation
Remarks
The above algorithm for k-VC is a kernelization algorithm
that returns an instance G with |E(G )| ∈ O(k2) and
|V(G)| ∈ O(k2).
We will sometimes (sloppily) ignore logarithmic factors and
call this an O(k2)-kernel; note however that at least
|E(G )| log |V(G )| = O(k2 log k) bits may be needed to
encode G .
For graph problems, vertex kernels are important: e.g.
suppose a graph G is returned with |E(G )| ≤ k2 and
|V(G )| ≤ ck: this is an O(k2)-kernel but a ck-vertex
kernel. Edge kernels are defined similarly.
Kernelization
Kernelization: Definition, Basic Facts, and Motivation
Equivalence between FPT-algorithms and
Kernelization
Theorem
A parameterized problem (P, κ) admits an FPT algorithm iff
there is a kernelization algorithm for (P, κ) (and (P, κ) is
decidable).
Kernelization
Kernelization: Definition, Basic Facts, and Motivation
Equivalence between FPT-algorithms and
Kernelization
Proof (→):
Suppose A is an FPT-algorithm for (P, κ) with running time
O(f(κ(X))(|X|)c) for an instance X of (P, κ). If |X| ≤ f(κ(X))
then X itself is a f(κ)-kernel. Hence, we can assume that
|X| > f(κ(X)). Note that in this case the algorithm A runs in
polynomial time because O(f(κ(X)(|X|)c)) ⊆ O((|X|)c+1).
Hence, we can modify A into a kernelization algorithm as
follows: If A returns YES then we return a trivial YES-instance
for (P, κ) and if A returns NO we return a trivial NO-instance for
(P, κ). Hence, we obtain an constant size kernel in this case
and altogether a f(κ)-kernel for (P, κ).
Kernelization
Kernelization: Definition, Basic Facts, and Motivation
Equivalence between FPT-algorithms and
Kernelization
Proof (←):
For the reverse direction suppose we are given a kernelization
algorithm A for the decidable problem (P, κ). Hence, running A
on an instance X of (P, κ) gives us a f(κ)-kernel X for some
arbitrary but computable function f : N → N. Because (P, κ) is
decidable we can then solve X by brute-forth in time
O(g(f(κ(X )))) ⊆ O(g(f(κ(X)))) for some arbitrary but
computable function g : N → N. Altogether we obtain the
required FPT-algorithm for (P, κ) with running time
O∗(g(f(κ(X)))).
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
Definition
MAXIMUM SATISFIABILITY (MAX SAT) Parameter: k
Input: A boolean CNF-formula F := m
i=1 Ci and a natural
number k.
Question: Is there a truth assignment for F that satisfies at
least k clauses?
Remark
The size of a CNF-formula is the sum of clause lengths, i.e., the
number of literals. That means we ignore logarithmic factors
again!
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
Trivial Clauses
Definition
A clause of F is trivial if it contains both a positive and a
negative literal of the same variable.
Observation
Let F be the CNF-formula obtained from F after removing all t
trivial clauses. Then (F, k) and (F , k − t) are equivalent.
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
Long Clauses
Definition
For an instance (F, k) a clause of F is long if it contains at least
k literals and short otherwise.
Theorem
If F contains at least k long clauses then (F, k) is a
YES-instance.
Proof:
Because every non-trival long clause contains at least k
variables you can choose a unique variable for each of the k
long clauses and satisfy the clauses by setting the choosen
unique variable accordingly.
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
Long Clauses
Theorem
Let (F, k) be an instance of Max Sat where F contains no trivial
clauses and exactly l ≤ k long clauses and let F be the
CNF-formula obtained from F by deleting the l long clauses.
Then (F, k) and (F , k − l) are equivalent.
Proof:
A truth assignment for F which satisfies at least k clauses,
satisfies at least k − l clauses of F . Furthermore, in a truth
assignment for F which satisfies k − l clauses, all expect at
most k − l variables are free to be changed. This allows us to
satisfy the remaining l long clauses.
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
Theorem
Let (F, k) be an instance of MAX SAT where F does not contain
trivial or long clauses. If F contains at least 2k clauses then
(F, k) is a YES-instance.
Proof:
Take an arbitrary truth assignment τ and its complement ¯τ.
Because every clause is satisfied either by τ or by ¯τ one of
them satisfies at least 2k
2 = k clauses.
Kernelization
A simple Kernel for MAXIMUM SATISFIABILITY
An O(k2
)-kernel for MAX SAT
The kernelization algorithm for MAX SAT on instance (F, k):
1. Let F contain exactly t trivial clauses. If t ≥ k return a
trivial YES-instance. Otherwise, let F be the formula
obtained from F by removing the t trivial clauses and let
k = k − t.
2. Let F contain exactly l long clauses. If l ≥ k return a
trivial YES-instance. Otherwise, let F be the formula
obtained from F after removing the l long clauses and let
k = k − l.
3. If F contains at least 2k clauses return a trivial
YES-instance. Otherwise, F contains at most 2k clauses
with at most k literals each. Hence (F , k ) is a
O(k k ) = O(k2)-kernel.
Kernelization
A simple Kernel for d-HITTING SET
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
A simple Kernel for d-HITTING SET
Definition
k-d-HITTING SET Parameter: k
Input: A hypergraph H = (V, E) with |e| ≤ d for every e ∈ E.
Question: Does H have a hitting set S with |S| ≤ k, i.e., a set
S of vertices of H such that S ∩ e = ∅ for every e ∈ E?
Remarks
Because k-VC is equivalent to k-2-HITTING SET, the
kernel for k-VC is a special case of the kernel for
k-d-HITTING SET.
The more general problem HITTING SET is W[2]-complete!
Kernelization
A simple Kernel for d-HITTING SET
Sunflowers
Definitions
Let H = (V, E) be a hypergraph. A k-subflower in H consists of
a set S = {e1, . . . , ek } ⊆ E and a core C ⊆ V such that
ei ∩ ej = C for every 1 ≤ i < j ≤ k. A hypergraph is d-uniform if
|e| = d for every e ∈ E.
Sunflower Lemma
Let H = (V, E) be a d-uniform hypergraph with more than
(k − 1)d d! edges. Then H has a k-sunflower which can be
found in polynomial time.
Kernelization
A simple Kernel for d-HITTING SET
Sunflower Lemma
Sunflower Lemma
Let H = (V, E) be a d-uniform hypergraph with more than
(k − 1)d d! edges. Then H has a k-sunflower which can be
found in polynomial time.
Proof:
By induction over d. If d = 1 then H has more than k − 1
disjoint edges which gives a k-sunflower. For d > 1 we use the
following induction hypothesis:
IH: Every (d − 1)-uniform hypergraph with more than
(k − 1)d−1(d − 1)! edges contains a k-sunflower.
Kernelization
A simple Kernel for d-HITTING SET
Sunflower Lemma
Proof, continued:
IH: Every (d − 1)-uniform hypergraph with more than
(k − 1)d−1(d − 1)! edges contains a k-sunflower.
Let F = {f1, . . . , fl} be a maximal set of disjoint hyperedges in
H. If l ≥ k then F is a sunflower with core ∅.
Otherwise, let W = l
i=1 fi then |W| ≤ (k − 1)d. H contains
more than (k − 1)d d! edges and every edges of H is hit by W.
Kernelization
A simple Kernel for d-HITTING SET
Sunflower Lemma
Proof, continued:
IH: Every (d − 1)-uniform hypergraph with more than
(k − 1)d−1(d − 1)! edges contains a k-sunflower.
Hence, there is an element w ∈ W that hits more than
(k−1)d d!
(k−1)d = (k − 1)d−1(d − 1)! edges. Taking all of these edges
and removing w from them yields a (d − 1)-uniform hypergraph
H with more than (k − 1)d−1(d − 1)! edges. By induction, H
contains a k sunflower S. Let C be its core. Taking the
corresponding edges in H yields a k-sunflower in H with core
C ∪ {w}.
Kernelization
A simple Kernel for d-HITTING SET
Sunflower Lemma
Remark
The proof of the Sunflower Lemma can be easily modified to a
polynomial time algorithm to find a k-sunflower in a hypergraph
H.
Kernelization
A simple Kernel for d-HITTING SET
A kernel for k-d-HITTING SET
Let F be a (k + 1)-sunflower with core C in hypergraph H and
let S be a hitting set of H.
If S ∩ C = ∅ then C has to hit all pedals of F so |S| ≥ k + 1.
Therefore, H has a hitting set of size k iff the hypergraph H
with edge set (E(H) \ F) ∪ {C} has a hitting set of size k.
Reduction rule: replace (H, k) by (H , k).
By the subflower lemma, a reduced hypergraph H contains:
at most (k − 1) edges of size 1;
at most (k − 1)22! edges of size 2;
. . .
at most (k − 1)d d! edges of size d.
Hence, it contains at most (k − 1)d d!d edges in total.
Kernelization
A simple Kernel for d-HITTING SET
A kernel for k-d-HITTING SET
Theorem
The above algorithm is a (k − 1)d d!d-edge kernelization for
k-d-HITTING SET.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
A Kernel for MAXIMUM LEAVES SPANNING TREE
Let G be a graph and v ∈ V(G):
Definitions
A subgraph H of G is spanning if V(H) = V(G).
G is a tree if it is connected and has no cycles.
A leaf of a (tree) is a vertex v with degree 1.
We denote by deg(v) the degree of the vertex v in G.
k-MAX LEAVES SPANNING TREE (k-LST) Parameter: k
Input: A connected graph G and a natural number k.
Question: Does G have a spanning tree with at least k leaves?
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Some further notions
Let G be a graph and {u, v} ∈ E(G).
Definition (Contraction)
G/{u, v} is the graph obtained from G after contracting the
edge {u, v} into a new vertex, i.e., G/{u, v} has vertex set
(V(G) \ {u, v}) ∪ {n} and edge set
{ {x, y} ∈ [V(G) \ {u, v}]2 : {x, y} ∈ E(G) }∪
{ {x, n} : x ∈ V(G) \ {u, v} and
({x, u} ∈ E(G) or {x, v} ∈ E(G)) }.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Some further notions
Let G be a graph and {u, v} ∈ E(G).
Definitions
G − {u, v} is the graph (V(G), E(G) \ {u, v}).
If G is connected then the edge {u, v} is a bridge if the
graph G − {u, v} is disconnected.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Reduction Rules
Degree 2 Rule
Let (G, k) be k-LST instance and let {u, v} ∈ E(G) with
deg(u) = deg(v) = 2. If G − {u, v} is connected, then
(G − {u, v}, k) is an equivalent instance.
Bridge Rule
Let (G, k) be k-LST instance and let {u, v} ∈ E(G) with
deg(u) ≥ deg(v) ≥ 2. If {u, v} is a bridge, then (G/{u, v}, k) is
an equivalent instance.
Consequently, a reduced instance (G, k) contains no adjacent
vertices of degree 2 and no bridges between vertices of degree
at least 2.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Reduction Rules
Theorem
A reduced connected graph G contains a spanning tree with at
least |V(G)|
5 leaves.
Proof:
Let T be a (possible non-spanning) subgraph of G that is a
tree. We define: n(T)=|V(T)|, l(T) is the number of leaves of F,
and d(T) is the number of dead leaves of T, i.e., the leaves of
T that have no neighbor outside of T. We first show that G
contains a subtree T with 4l(T) + d(T) ≥ n(T). W.l.o.g. G
contains a vertex v with degree at least 3. Then v together with
its neighbors is such a tree.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Reduction Rules
Theorem
A reduced connected graph G contains a spanning tree with at
least |V(G)|
5 leaves.
Proof, continued:
Given a tree T with 4l(T) + d(T) ≥ n(T), a larger tree T with
4l(T ) + d(T ) ≥ n(T ) exists if:
(A) T contains a vertex with at least 2 neighbors not in T, or a
non-leaf with at least 1 neighbor not in T;
(B) If (A) does not apply but there is a vertex outside of T with
either at least 2 neighbors in T, or with degree 1.
(C) If there is a vertex outside of T with exactly one neighbor in
T and degree at least 3.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Reduction Rules
Theorem
A reduced connected graph G contains a spanning tree with at
least |V(G)|
5 leaves.
Proof, continued:
(D) If (B) and (C) do not apply but T is not yet spanning. Then
there is u inside of T with at least 1 neighbor inside and 1
neighbor v outside of T and with degree exactly 2.
Furthermore, the degree of v cannot be 1 (otherwise u and
its other neighbor would form a bridge) and also not 2
(otherwise u and v would be degree 2 neighbors). Hence,
v has degree at least 3 and no neighbors in T ((C)).
Consequently, we can add v and its neighbors to T.
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
Reduction Rules
Theorem
A reduced connected graph G contains a spanning tree with at
least |V(G)|
5 leaves.
Proof, continued:
Hence, a spanning tree with 4l(T) + d(T) ≥ n(T) exists.
Because d(T) = l(T) in any spanning tree we get l(T) ≥ n
5 .
Kernelization
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING TREE
A 5k-vertex kernel for k-Leaf Spanning Tree
The following algorithm gives a 5k-vertex kernel for a k-LST
instance (G, k):
Apply the degree 2 rule and the bridge rule until an equivalent
irreducible instance (G , k ) is obtained.
If G has more than 5k vertices we can return a trivial
YES-instance and otherwise G is the kernel.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
A 2k-Vertex Kernel for Vertex Cover
MINIMUM VERTEX COVER as an Integer Programm
Let G be an undirected graph with vertices V(G) = {v1, . . . , vn}
and k a natural number. Then the k-VERTEX COVER problem
for (G, k) can be written as follows:
VC-ILP: min n
i=1 xi
s.t. xi + xj ≥ 1 ∀{vi, vj} ∈ E(G)
xi ∈ {0, 1} ∀i ∈ {1, . . . , n}
Here a 0/1-variable xi determines whether the vertex vi is
taken into the vertex cover.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
VC-IPL Relaxation
Let G be an undirected graph with vertices V(G) = {v1, . . . , vn}
and k a natural number. Then the Half-Integer Relaxation of the
k-VERTEX COVER problem for (G, k) can be written as follows:
VC-REL: min n
i=1 xi
s.t. xi + xj ≥ 1 ∀{vi, vj} ∈ E(G)
xi ∈ {0, 1
2 , 1} ∀i ∈ {1, . . . , n}
Here a 0/1-variable xi determines whether the vertex vi is
taken into the vertex cover.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
VC-REL
How does VC-REL help us to construct a kernel for VC? We
need to answer the following questions:
Question (1)
How can we find an optimal solution to VC-REL?
Question (2)
How can an optimal solution for VC-REL be used to construct a
2k-vertex kernel for k-VC?
We start by answering Question (2).
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Some Properties of VC-REL
Let η : {x1, . . . , xn} → {0, 1
2 , 1} be an optimal solution to
VC-REL on the graph G and define Vj = { vi : η(xi) = j } for
every j ∈ {0, 1
2 , 1}.
Property (1)
If C is a vertex cover for G[V1
2
], then C ∪ V1 is a VC for G.
Property (2)
G[V1
2
] has no VC of size less than
|V 1
2
|
2 .
Property (3)
There is a minimum VC C of G with V1 ⊆ C.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Some Properties of VC-REL
Let η : {x1, . . . , xn} → {0, 1
2 , 1} be an optimal solution to
VC-REL on the graph G and define Vj = { vi : η(xi) = j } for
every j ∈ {0, 1
2 , 1}.
Property (1)
If C is a vertex cover for G[V1
2
], then C ∪ V1 is a VC for G.
Proof:
Clearly all edges with at least 1 endpoint in V1 and all edges
with both endpoints in V1
2
are covered by C ∪ V1. Hence, the
only edges remaining are the edges with both endpoints in V0
or 1 endpoint in V0 and the other in V1
2
. However, because η is
a solution of VC-REL such edges can not exist.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Some Properties of VC-REL
Let η : {x1, . . . , xn} → {0, 1
2 , 1} be an optimal solution to
VC-REL on the graph G and define Vj = { vi : η(xi) = j } for
every j ∈ {0, 1
2 , 1}.
Property (2)
G[V1
2
] has no VC of size less than
|V 1
2
|
2 .
Proof:
Suppose not and let C be a VC of G[V1
2
] of size less than
|V 1
2
|
2 .
Because of Property (1) C ∪ V1 is a vertex cover of G. Hence,
η with η (xi) = 1 if vi ∈ C ∪ V1 and η (xi) = 0 otherwise is a
solution to VC-REL and n
i=0 η (xi) < |V1| + 1
2 |V1
2
| = n
i=0 η(xi)
contradicting the minimality of η.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Some Properties of VC-REL
Let η be an optimal solution to VC-REL on the graph G and
define Vj = { vi : η(xi) = j } for every j ∈ {0, 1
2 , 1}.
Property (3)
There is a minimum VC C of G with V1 ⊆ C.
Proof:
Let C be a minimum VC of G. We first show that
|C ∩ V0| ≥ |V1 \ C|. Let η : {x1, . . . , xn} → {0, 1
2, 1} such that
η (xi) = 1
2 if vi ∈ (C ∩ V0) ∪ (V1 \ C) and η (xi) = η (xi),
otherwise. We claim that η is a solution to VC-REL.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Some Properties of VC-REL
Let η be an optimal solution to VC-REL on the graph G and
define Vj = { vi : η(xi) = j } for every j ∈ {0, 1
2 , 1}.
Property (3)
There is a minimum VC C of G with V1 ⊆ C.
Proof, continued:
Consider an edge {vi, vj}. If {vi, vj} ⊆ V1
2
∪ V1 then
η (xi) + η (xj) ≥ 1
2 + 1
2 = 1. Hence, w.l.o.g. we can assume that
vi ∈ V0. Then vj ∈ V1 (otherwise η would not be feasable). If
vj ∈ C then η (xj) = 1. Otherwise, because C is a vertex cover
vi ∈ C and hence η (vi) + η (vj) = 1
2 + 1
2 = 1.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Some Properties of VC-REL
Let η be an optimal solution to VC-REL on the graph G and
define Vj = { vi : η(xi) = j } for every j ∈ {0, 1
2 , 1}.
Property (3)
There is a minimum VC C of G with V1 ⊆ C.
Proof, continued:
Because η is an optimal solution to VC-REL, we obtain:
0 ≤ i η (xi) − i η(xi) = 1
2 |C ∩ V0| − 1
2 |V1 \ C|
Hence, |V1 \ C| ≤ |C ∩ V0|, as required.
Consider the set C := (C \ V0) ∪ V1. It follows that |C | ≤ |C|. It
is now easy to see that C is a VC of G which concludes the
proof.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
A 2k-Vertex Kernel for Vertex Cover
Hence, we have:
(1) If C is a vertex cover for G[V1
2
], then C ∪ V1 is a VC for G.
(2) G[V1
2
] has no VC of size less than
|V 1
2
|
2 .
(3) There is a minimum VC C of G with V1 ⊆ C.
This allows for the following 2k-Vertex Kernelization Algorithm:
Let (G, k) be a k-VC instance and let η be an optimal solution
to the corresponding VC-REL problem. Consider (G , k ) with
G = G[V1
2
] and k = k − |V1|. Because of Property (1) and
Property (3) the two instances are equivalent. Furthermore,
because of Property (2) (G , k ) contains at most 2k vertices,
otherwise we can return a trivial NO-instance.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Solving VC-REL
Question (1)
How can we find an optimal solution to VC-REL?
There are (at least) 2 answers to this question.
Answer (1)
Relax VC-REL further to a linear program that can be solved in
polynomial time. One can now show that such a real-valued
solution can be efficiently transformed to a VC-REL solution of
the same value.
Answer (2)
Using matchings in bipartite graphs.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Solving VC-REL using Matchings
Definition
A graph G is bipartite if there is a partition {A, B} of V(G) such
that all edges of G have 1 endpoint in A and 1 endpoint in B. A
and B are the sides or parts of G.
Let G be a graph. We denote by B(G) the bipartite graph
obtained from G that has vertex set { v, v : v ∈ V(G) } and
edge set { (u, v ), (u , v) : {u, v} ∈ E(G) }.
Lemma
VC-REL on G has a solution η with i η(xi) = z iff B has a
vertex cover C with |C| = 2z.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Solving VC-REL using Matchings
Lemma
VC-REL on G has a solution η with i η(xi) = z iff B(G) has a
vertex cover C with |C| = 2z.
Proof:
Let η be a solution for VC-REL on G. We set
C := { vi, vi : η(xi) = 1 } ∪ { vi : η(xi) = 1
2 }. To show that C is a
VC of G consider an edge {vi, vj } ∈ E(B(G)). Clearly, C covers
this edge as long as η(xi) = 0. Furthermore, if η(xi) = 0 then
η(xj) = 1 (because η is a solution and {vi, vj} ∈ E(G)). Hence,
vj ∈ C.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Solving VC-REL using Matchings
Lemma
VC-REL on G has a solution η with i η(xi) = z iff B has a
vertex cover C with |C| = 2z.
Proof:
For the reverse direction let C be a vertex cover of B(G). We
define η such that η(xi) = 1 if vi, vi ∈ C, η(xi) = 1
2 if either
vi ∈ C or vi ∈ C and η(xi) = 0, otherwise.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Solving VC-REL using Matchings
Lemma
VC-REL on G has a solution η with i η(xi) = z iff B has a
vertex cover C with |C| = 2z.
Proof, continued:
We claim that η is a solution to VC-REL of G. Consider an edge
{vi, vj} ∈ E(G). Because C covers both {vi, vj } and {vi , vj} one
of the following holds:
vi ∈ C and vi ∈ C. Then η(xi) = 1.
vj ∈ C and vj ∈ C. Then η(xj) = 1.
vi ∈ C and vj ∈ C. Then η(xi) ≥ 1
2 and η(xj) ≥ 1
2 .
vi ∈ C and vj ∈ C. Then η(xi) ≥ 1
2 and η(xj) ≥ 1
2 .
Kernelization
A 2k-Vertex Kernel for Vertex Cover
König’s Theorem
Theorem
Let G be a bipartite graph. Then the size of a minimum vertex
cover equals the size of a maximum matching, and both can be
found in polynomial time.
The previous Lemma now allows us to compute an optimal
solution to VC-REL for a graph G by computing a maximum
matching (minimum vertex cover) in the bipartite graph B(G).
Kernelization
A 2k-Vertex Kernel for Vertex Cover
König’s Theorem
Definition
A matching in a graph G is a set of edges M ⊆ E(G) that share
no end vertices (every v ∈ V(G) is incident with at most 1 edge
of M). A vertex v ∈ V(G) is saturated by M if it is incident with
an edge of M.
Definition
Let B be a graph with a matching M. A path P in B is alternating
if its edges are alternatingly in M and not in M. An alternating
path is augmenting if its end vertices are not saturated by M.
Berge’s Theorem
Let G be a graph with matching M. Then M is maximum iff G
contains no augmenting path.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Proof of König’s Theorem
Theorem
The size of a MVC equals the size of a MM on a bipartite graph.
Proof:
Because every edge of a matching needs to be covered by any
vertex cover it trivially holds that |M| ≤ |C| for any matching M
and any VC C.
Hence, it remains to show that |C| ≤ |M|.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Proof of König’s Theorem
Proof, continued:
The following algorithm finds a MVC C and a MM M with
|C| = |M| on a bipartite graph B with parts V and V :
(1) Start with C = V and M = ∅.
(2) If |C| = |M| then return C and M, halt.
(3) Choose an unsaturated vertex v ∈ C and construct an
alternating search tree subgraph T of B, rooted at v.
(4) If T contains an augmenting path P, then augment M
using P, goto (2).
(5) Otherwise, find a vertex set S with v ∈ S such that: N(S)
is saturated and |N(S)| < |S|. Then C := (C \ S) ∪ N(S)
is a VC with |C | < |C|. Set C := C , goto (2).
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Hall’s Theorem
The following theorem also follows:
Hall’s Theorem
A bipartite graph B with sides V and V has a matching
saturating V iff there is no S ⊆ V with |N(S)| < |S|.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Summary
In polynomial time we can find a matching M and a VC C
with |M| = |C|, which therefore are maximum resp.
minimum.
By applying this procedure to the bipartite graph B
constructed from G, we can solve VC-REL on G in
polynomial time.
This concludes the 2k-vertex kernelization for k-VC.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
A Kernel for VC using Crowns
Definition
A crown in a graph G is a triple (I, H, M) such that:
C1 I ⊆ V(G) is an independent set;
C2 N(I) ⊆ H;
C3 M is a matching (between I and H) that saturates H.
Theorem
Let G be a graph and η an optimal solution to VC-REL of G
where V1 = ∅. Then there is a matching M between V0 and V1
such that (V0, V1, M) is a crown of G.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
A Kernel for VC using Crowns
Theorem
Let G be a graph and η an optimal solution to VC-REL of G
where V1 = ∅. Then there is a matching M between V0 and V1
such that (V0, V1, M) is a crown of G.
Proof:
Clearly, Properties C1 and C2 are trivially satisfied by V0 and
V1. Furthermore, as we have shown before (Property (3)) that
V1 is a minimum vertex cover for G[V1 ∪ V0] − E[V1] which by
Koenig’s Theorem implies Property C3.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
A Kernel for VC using Crowns
Theorem
Let G be a graph containing a crown (I, H, M) with |H| < |I|.
Then an optimal solution for VC-REL to G gives us a crown for
G.
Proof:
The crown (I, H, M) with |H| < |I| ensures that VC-REL has a
solution η with value at most
|H| + 1
2 |V(G) \ (I ∪ H)| < 1
2 |V(G)|/2. Hence (unless G contains
isolated vertices), we obtain that V1 = ∅ for an optimal solution
η which gives us a crown for G.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
A Kernel for VC using Crowns
We have seen before that if (I, H, M) is a crown of G, then
(G, k) and (G \ (I ∪ H), k − |I|) are equivalent k-VC
instances.
Furthermore, if G contains no crown (I, H, M) with
|H| < |I|, then every VC S of G has size at least |V|
2 .
Conclusion
A different way to express the 2k-vertex kernel for k-VC: find
crowns (I, H, M) with |H| < |I| in polynomial time if they exist
and reduce them. A crownless graph is a 2k-kernel.
Remark
Crown reductions have also been used to find kernelizations for
other problems.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
An Alternative 3k-Vertex Kernel for VC
Lemma
Let G be a graph without isolated vertices and k be a natural
number. Then in polynomial time we can either:
find a matching of size k + 1;
find a crown decomposition;
or conclude that the graph has at most 3k vertices.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
An Alternative 3k-Vertex Kernel for VC
Lemma
Let G be a graph without isolated vertices and k be a natural
number. Then in polynomial time we can either:
find a matching of size k + 1; → No solution!
find a crown decomposition; → Reduce!
or conclude that the graph has at most 3k vertices. →
3k-vertex kernel!
Kernelization
A 2k-Vertex Kernel for Vertex Cover
An Alternative 3k-Vertex Kernel for VC
Proof:
Greedily find a maximimal matching M of G. If |M| > k then we
are done. Consider the bipartite graph B with partition
{I := G \ V[M], H := V[M]} obtained from G after deleting all
edges between vertices in V[M]. Because M is maximal in G it
follows that I is an independent set in G (and also in B). Find a
minimum vertex cover C of B (using Koenig’s Theorem this can
be done in polynomial time). If C contains a vertex from H then
we obtain a crown decomposition. Otherwise C contains all
vertices of I hence G contains at most 2k + k vertices.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Dual of Vertex Coloring
SAVING k-COLORS Parameter: k
Input: A graph G and a natural number k.
Question: Does G have a vertex coloring with |V(G)| − k
colors?
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Dual of Vertex Coloring
Lemma
Let I := (G, k) be an instance of SAVING k-COLORS and
(I, H, M) be a crown decomposition of the complement of G.
Then I and I := (G \ (I ∪ H), k − |H|) are equivalent instances
of SAVING k-COLORS.
Proof:
Let I and (I, H, M) be as above. Then I is a clique in G and
hence every vertex in I has to be colored with a different color.
Furthermore, because of the matching M the vertices in H can
be colored using only these |I| colors and none of these colors
can be used for G \ (I ∪ H).
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Dual of Vertex Coloring
Lemma
Let (G, k) be an instance of SAVING k-COLORS and let ¯G be
the complement of G. Then in polynomial time we can either:
find a matching of size k + 1 in ¯G;
find a crown decomposition of ¯G;
or conclude that the graph ¯G has at most 3k vertices.
This gives a 3k-vertex kernel for SAVING k-COLORS.
Kernelization
A 2k-Vertex Kernel for Vertex Cover
Dual of Vertex Coloring
Lemma
Let (G, k) be an instance of SAVING k-COLORS and let ¯G be
the complement of G. Then in polynomial time we can either:
find a matching of size k + 1 in ¯G; → Yes, we can save k
colors!
find a crown decomposition of ¯G; → Reduce!
or conclude that the graph ¯G has at most 3k vertices. →
3k-vertex kernel!
This gives a 3k-vertex kernel for SAVING k-COLORS.
Kernelization
Kernelization and Approximation
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
Kernelization and Approximation
Using Kernelization for Approximation
Definition
An α-approximation algorithm for a minimization (maximization)
problem P is a polynomial time algorithm that returns a solution
S for P such that value(S) ≤ αvalue(OPT)
(value(S) ≥ 1
α value(OPT)), where OPT is an optimal solution.
Observation
The 2k-kernelization algorithm for a graph G gives a
2-approximation algorithm for VERTEX COVER as follows:
Compute an optimal solution η to VC-REL of G. Then V1
2
∪ V1 is
a vertex cover of G of size at most 2 times the optimal solution.
Kernelization
Kernelization and Approximation
Using Kernelization for Approximation
Remark
ck-vertex kernels for “vertex subset” problems usually yield
c-approximation algorithms for the corresponding optimization
problem.
Example
For MAXIMUM LEAVES SPANNING TREE, the 5k-vertex
kernelization gives a 5-approximation algorithm.
Kernelization
Combining Search Tree and Kernelization
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
Combining Search Tree and Kernelization
Combining Search Tree and Kernelization
Let P be a parameterized problem such that:
P has a bounded search algorithm with branching number
α and PS(|X|) is the time spend at each node of the search
tree.
P has a p(k)-kernelization algorithm with running time
PK (|X|) where p(k) is some polynomial in k.
for every instance (X, k) of P. Then the bounded search tree
algorithm has a running time of O(αk PS(|X|)). Furthermore, if
we first apply kernelization and then run the bounded search
tree algorithm on the kernel we obtain a running time of
O(PK (|X|) + PS(q(k))αk ).
Kernelization
Combining Search Tree and Kernelization
Combining Search Tree and Kernelization
Theorem
Let P be a parameterized problem such that:
P has a bounded search algorithm with branching number
α and PS(|X|) is the time spend at each node of the search
tree.
P has a p(k)-kernelization algorithm with running time
PK (|X|) where p(k) is some polynomial in k.
for every instance (X, k) of P. Then an algorithm that runs the
kernelization algorithm at each node of the search tree has
running time O(PK (|X|) + αk )
Kernelization
Combining Search Tree and Kernelization
Combining Search Tree and Kernelization
Proof, sketch:
For the combination of search tree and kernelization as outlined
above, the recurrence function becomes:
T(k) = T(k − d1) + · · · + T(k − dl) + PK (p(k)) + PS(p(k))
Because p(k) is polynimimial in k we obtain:
T(k) = T(k − d1) + · · · + T(k − dl) + P(k)
for some arbitrary polynomial P(k). It can be shown that T(k)
is bounded by αk .
Kernelization
Summary
Outline
1 Kernelization
Introduction
A Simple Kernel for VERTEX COVER
Kernelization: Definition, Basic Facts, and Motivation
A simple Kernel for MAXIMUM SATISFIABILITY
A simple Kernel for d-HITTING SET
A 5k-Vertex Kernel for MAXIMUM LEAVES SPANNING
TREE
A 2k-Vertex Kernel for Vertex Cover
Kernelization and Approximation
Combining Search Tree and Kernelization
Summary
Kernelization
Summary
Kernelization: Summary
Kernelization algorithms are a method to obtain FPT
algorithms.
Every problem in FPT has a kernelization algorithm. One
is hence mostly interested in finding small (polynomial)
kernels.
Kernelization algorithms are preprocessing algorithms that
can add to any algorithmic method (e.g. approximation
algorithms).
Kernelization algorithms usually consist of reduction rules
which reduce simple local structures and a bound f(k) for
irreducible instances that allows us to return No or Yes
depending on the size of the instance.
Kernelization
Summary
Designing Kernelization Algorithms
What are the trivial substructures, where an optimal
solution of a certain form can be guaranteed?
Is there a reduction rule reflecting this?
Can a bound be proved for irreducible instances? If not,
which structures are problematic? . . .