Biology Reference
In-Depth Information
rameter
k
—and ask whether there is an algorithm that confines the combinatorial
explosion that is involved in solving the problem to the parameter.
Definition 1.1.
An instance of a parameterized problem consists of a problem in-
stance
I
and a parameter
k
. A parameterized problem is
fixed-parameter tractable
if it can be solved in
f
(
k
)
O
(1)
time, where
f
is a computable function solely
depending on the parameter
k
, and not on the input size
·|
I
|
|I|
.
For NP-hard problems,
f
(
k
) will of course not be polynomial, since otherwise
we would have an overall polynomial-time algorithm.
As parameterized complexity theory points out, there are problems that are
likely not to be fixed-parameter tractable [25, 30, 60]. It is important to note in
this respect that a problem can have
various
parameterizations such as the size
of the solution that is sought after or some structural parameter that characterizes
the input. A problem that is not fixed-parameter tractable with respect to some
parameter may still be so with respect to others. Also, the choice of the parameter
can greatly affect the efficiency of the algorithm that is obtained.
Besides the classic reference [25], two new monographs are available on pa-
rameterized complexity, one focusing on theoretical foundations [30] and one fo-
cusing on techniques and algorithms [60].
1.2.1.
Kernelizations
Before firing up a computationally expensive algorithm to solve a combinatorially
hard problem, one should always try to perform a
reduction
on the input data, the
idea being to quickly presolve those parts of the input data that are relatively easy
to cope with and thus to shrink the input to those parts that form the “really hard”
core of the problem. Costly algorithms need then only be applied to the reduced
instance. In some practical scenarios, data reduction may even reduce a seemingly
hard problem to triviality [35, 56, 70].
Clearly, practitioners are likely to already be aware of data reduction rules.
The reason why they should also consider fixed-parameter tractability in this con-
text is that fixed-parameter theory provides a way to use data reduction rules not
only in a heuristic way, but to
prove their power
by so-called
kernelizations
.These
run in polynomial time and give an upper bound on the size of a reduced instance
that solely depends on the parameter value, that is, they come with a performance
guarantee both concerning their running time as well as their effectiveness. Hav-
ing a quantitative measure for the performance of a data reduction can moreover
help to guide the search for further improved data reductions in a constructive
way [39].
Search WWH ::
Custom Search