Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Weak Kernels

RSS-Feed




Revision #7
Authors: Haitao Jiang, Chihao Zhang, Binhai Zhu
Accepted on: 23rd September 2012 18:42
Downloads: 687
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
Downloads: 693
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
Downloads: 826
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
Downloads: 1086
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
Downloads: 1251
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
Downloads: 1194
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
Downloads: 1325
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
Downloads: 1440
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