In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

We tune some definitions to make them more precise. We also differentiate indirect and direct weak kernels --- based on the past experience, the latter can be converted to the traditional kernels.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

We tune the definitions a bit (making them more precise). Also, we differentiate indirect weak kernels and direct weak kernels --- based on the experience in the past two years, the latter can be converted into the traditional kernels.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

One of the applications (CMSR) was deleted from the
paper, hopefully, this is the last revision on ECCC.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for (NP-hard) search problems, which
is about search space reduction and stands as a new generic technique
for designing FPT algorithms. We show that weak kernels are
different from the (traditional) kernels for decision problems, by
exhibiting an example out of $\P$ such that its decision version
has no kernel while the equivalent search problem has a weak kernel.
We show a few applications of weak kernels, for which a traditional
kernelization seems hard to apply. Among them, we present the first
FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

In response to some comments, we formalize the concept of search problems and search space. No bound/detail in the applications is changed. Chihao Zhang is added as a co-author.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

The weak kernelization for CMSR misses 2 cases (inherited from a previous algorithm we try to revise). This was covered in this version. No bound is changed.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.

In this paper, we formalize a folklore concept and formally define
{\em weak kernels} for fixed-parameter computation. We show that a
problem has a (traditional) kernel then it also has a weak kernel.
It is unknown yet whether the converse is always true. On the other hand,
for a problem in NP, if it has a weak kernel then it admits an FPT algorithm
(hence a kernel). We show a few applications of weak kernels, for which a
(traditional) kernelization seems hard to apply. Among them, we present the
first FPT algorithm for the famous Sorting by Minimum Unsigned Reversals
problem.