Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #7 to TR10-005 | 23rd September 2012 18:42

#### Weak Kernels

Revision #7
Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu
Accepted on: 23rd September 2012 18:42
Keywords:

Abstract:

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.

Changes to previous version:

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.

Revision #6 to TR10-005 | 23rd September 2012 18:36

#### Weak Kernels

Revision #6
Authors: Binhai Zhu, Haitao Jiang, Chihao Zhang
Accepted on: 23rd September 2012 18:36
Keywords:

Abstract:

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.

Revision #5 to TR10-005 | 23rd September 2012 18:32

#### Weak Kernels

Revision #5
Authors: Haitao Jiang, Binhai Zhu
Accepted on: 23rd September 2012 18:32
Keywords:

Abstract:

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.

Changes to previous version:

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.

Revision #4 to TR10-005 | 10th October 2010 01:20

#### Weak Kernels

Revision #4
Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu
Accepted on: 10th October 2010 01:20
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #3 to TR10-005 | 14th September 2010 02:11

#### Weak Kernels

Revision #3
Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu
Accepted on: 14th September 2010 02:11
Keywords:

Abstract:

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.

Changes to previous version:

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.

Revision #2 to TR10-005 | 5th May 2010 02:45

#### Weak Kernels

Revision #2
Authors: Haitao Jiang, Binhai Zhu
Accepted on: 5th May 2010 02:45
Keywords:

Abstract:

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.

Changes to previous version:

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.

Revision #1 to TR10-005 | 9th January 2010 05:30

#### Weak Kernels

Revision #1
Authors: Haitao Jiang, Binhai Zhu
Accepted on: 9th January 2010 05:30
Keywords:

Abstract:

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.

### Paper:

TR10-005 | 3rd January 2010 17:29

#### Weak Kernels

TR10-005
Authors: Haitao Jiang, Binhai Zhu
Publication: 8th January 2010 10:21
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint