Biology Reference
In-Depth Information
1.2.1.2.
The Kernelization Concept
Abstractly speaking, what have we done in the previous section? After applying a
number of rules
in polynomial time
to an instance of V
ERTEX
C
OVER
, we arrived
at a reduced instance whose size can
solely be expressed in terms of the parame-
ter
k
. Since this can be easily done in
O
(
n
) time, we have found a data reduction
for V
ERTEX
C
OVER
with guarantees concerning its running time as well as its
effectiveness. These properties are formalized in the concepts of a
problem kernel
and the corresponding
kernelization
[25].
Definition 1.2.
Let
consists of input
pairs (
I,k
),where
I
is the problem instance and
k
is the parameter. A
reduction
to a problem kernel
(or
kernelization
) means to replace an instance (
I,k
) by a
reduced
instance (
I
,k
) called
problem kernel
in polynomial time such that
L
be a parameterized problem, that is,
L
(1)
k
≤
k
,
(2)
I
is smaller than
g
(
k
) for some function
g
only depending on
k
,and
(3) (
I,k
) has a solution if and only if (
I
,k
) has one.
While this definition does not formally require that it is possible to reconstruct
a solution for the original instance from a solution for the problem kernel, all
kernelizations we are aware of easily allow for this.
The methodological approach of kernelization, including various techniques
of data reduction, is best learned by the concrete examples that we discuss in
Sec. 1.3; there, we will also discuss kernelizations for V
ERTEX
C
OVER
that even
yield a kernel with a
linear
number of vertices in
k
.
To conclude this section, we state some useful general observations and re-
marks concerning Definition 1.2 and its connections to fixed-parameter tractabil-
ity. Most notably, there is a close connection between fixed-parameter tractable
problems and those problems that have a problem kernel—they are exactly the
same.
Theorem 1.1 (Cai et al. [11]).
Every fixed-parameter tractable problem is ker-
nelizable and vice-versa.
Unfortunately, the practical use of this theorem is limited: the running times of
a fixed-parameter algorithm directly obtained from a kernelization is usually not
practical; and, in the other direction, the theorem does not constructively provide
us with a data reduction scheme for a fixed-parameter tractable problem. Hence,
the main use of Theorem 1.1 is to establish the fixed-parameter tractability or
amenability to kernelization of a problem—or show that we need not search any
Search WWH ::
Custom Search