کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
430222 | 687929 | 2014 | 9 صفحه PDF | دانلود رایگان |
• We obtain a tight linear kernel for the NP-complete problem CMSR.
• We first try to obtain a direct weak kernel (or search space) for the solution.
• Different from many FPT algorithms, most of our rules are not local.
• We show once more that a direct weak kernel can be converted to a kernel.
In this paper, we compute the first linear kernel for the complementary problem of Maximal Strip Recovery (CMSR) — an NP-hard problem in computational genomics. Let k be the parameter which represents the size of the solution. The core of the technique is to first obtain a tight 18k bound (for the method) on the parameterized solution search space, which is done through a mixed global rules and local rules, and via an inverse amortized analysis. Then we apply additional data-reduction rules to obtain a 78k kernel for the problem, which is again tight for the method. Combined with the known algorithm using bounded degree search, we obtain the best Fixed-Parameterized-Tractable algorithm for CMSR to this date, running in O(2.36kk2+n2)O(2.36kk2+n2) time.
Journal: Journal of Computer and System Sciences - Volume 80, Issue 7, November 2014, Pages 1350–1358