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 j 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 74 k + 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 42 k + 24.

Authors

• Wenjun Li
• Haiyan Liu
• Jianxin Wang
• Lingyun Xiang School of Computer and Communication Engineering, Changsha University of Science and Technology
• Yongjie Yang

Keywords

• Complementary maximal strip recovery
• Linear kernel
• Kernelization
• Fixed-parameter tractable