An improved linear kernel for complementary maximal strip recovery: Simpler and smaller

摘要

We study the COMPLEMENTARY MAXIMAL STRIP RECOVERY problem (CMSR), where the given are two strings S-1 and S-2 of distinct letters, each of which appears either in the positive form or the negative form. The question is whether there are k letters whose deletion results in two matched strings. String S-1 matches string S-2 if there are partitions of S-1 and S-2 such that each component of the partitions contains at least two letters and, moreover, for each component S-1(i) of the partition of S-1, there is a unique component S-2(i); in the partition of S-2 which is either equal to S(1)(i )or can be obtained from S-1(i) by firstly reversing the order of the letters and then negating the letters. The CMSR problem is known to be NP-hard and fixed-parameter tractable with respect to k. In particular, a linear kernel of size 74k + 4 was developed based on 8 reduction rules. Very recently, by imposing 3 new reduction rules to the previous kernelization, the linear kernel has been improved to 58k. We aim to simplify the kernelization, yet obtain an improved kernel. In particular, we study 7 reduction rules which lead to a linear kernel of size 42k + 24. (C) 2018 Elsevier B.V. All rights reserved.