ECCC-Report TR10-005https://eccc.weizmann.ac.il/report/2010/005Comments and Revisions published for TR10-005en-usSun, 23 Sep 2012 18:42:52 +0200
Revision 7
| Weak Kernels |
Haitao Jiang,
Chihao Zhang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005#revision7In 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.Sun, 23 Sep 2012 18:42:52 +0200https://eccc.weizmann.ac.il/report/2010/005#revision7
Revision 6
| Weak Kernels |
Binhai Zhu,
Haitao Jiang,
Chihao Zhang
https://eccc.weizmann.ac.il/report/2010/005#revision6In 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.Sun, 23 Sep 2012 18:36:37 +0200https://eccc.weizmann.ac.il/report/2010/005#revision6
Revision 5
| Weak Kernels |
Haitao Jiang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005#revision5In 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.Sun, 23 Sep 2012 18:32:37 +0200https://eccc.weizmann.ac.il/report/2010/005#revision5
Revision 4
| Weak Kernels |
Haitao Jiang,
Chihao Zhang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005#revision4In 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.Sun, 10 Oct 2010 01:20:37 +0200https://eccc.weizmann.ac.il/report/2010/005#revision4
Revision 3
| Weak Kernels |
Haitao Jiang,
Chihao Zhang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005#revision3In 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.Tue, 14 Sep 2010 02:11:57 +0200https://eccc.weizmann.ac.il/report/2010/005#revision3
Revision 2
| Weak Kernels |
Haitao Jiang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005#revision2In 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.Wed, 05 May 2010 02:45:36 +0300https://eccc.weizmann.ac.il/report/2010/005#revision2
Revision 1
| Weak Kernels |
Haitao Jiang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005#revision1In 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.Sat, 09 Jan 2010 05:30:02 +0200https://eccc.weizmann.ac.il/report/2010/005#revision1
Paper TR10-005
| Weak Kernels |
Haitao Jiang,
Binhai Zhu
https://eccc.weizmann.ac.il/report/2010/005In 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.Fri, 08 Jan 2010 10:21:11 +0200https://eccc.weizmann.ac.il/report/2010/005