Revision #7 Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu

Accepted on: 23rd September 2012 18:42

Downloads: 1963

Keywords:

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.

Revision #6 Authors: Binhai Zhu, Haitao Jiang, Chihao Zhang

Accepted on: 23rd September 2012 18:36

Downloads: 2150

Keywords:

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 Authors: Haitao Jiang, Binhai Zhu

Accepted on: 23rd September 2012 18:32

Downloads: 2268

Keywords:

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.

Revision #4 Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu

Accepted on: 10th October 2010 01:20

Downloads: 2471

Keywords:

{\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.

Revision #3 Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu

Accepted on: 14th September 2010 02:11

Downloads: 2656

Keywords:

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.

Revision #2 Authors: Haitao Jiang, Binhai Zhu

Accepted on: 5th May 2010 02:45

Downloads: 2508

Keywords:

{\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.

Revision #1 Authors: Haitao Jiang, Binhai Zhu

Accepted on: 9th January 2010 05:30

Downloads: 2748

Keywords:

{\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.

TR10-005 Authors: Haitao Jiang, Binhai Zhu

Publication: 8th January 2010 10:21

Downloads: 2837

Keywords:

{\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.