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

Accepted on: 23rd September 2012 18:42

Downloads: 1569

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: 1698

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: 1840

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: 2084

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: 2248

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: 2125

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: 2306

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: 2405

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.