An Improved Linear Kernal for Complementary Maximal Strip Recovery: Simpler and Smaller
An Improved Linear Kernal for Complementary Maximal Strip Recovery: Simpler and Smaller
复制标题
用于互补最大条带恢复的改进线性内核：更简单、更小
DOI：
10.1016/j.tcs.2018.04.020
复制
发表时间：
--
影响因子：
1.1
通讯作者：
Yongjie Yang
中科院分区：
文献类型：
--
作者：
Wenjun Li;Haiyan Liu;Jianxin Wang;Lingyun Xiang;Yongjie Yang
本文研究互补最大条带恢复问题（CMSR），给定两个不同字母的字符串S1和S2，每个字符串以正形式或负形式出现。问题是是否有k个字母的删除会导致两个匹配的字符串。如果存在S1和S2的分区，使得分区的每个分量包含至少两个字母，并且此外，对于S1的分区的每个分量S1 i，在S 2的分区中存在唯一分量S 2 j，其等于S 1 i或者可以通过首先颠倒字母的顺序从S 1 i获得，并且然后否定这些字母已知CMSR问题是NP-难的，并且相对于k是固定参数的。特别地，基于8个约简规则开发了大小为74 k+ 4的线性核。最近，通过对以前的核化施加3个新的约简规则，线性核已经改进到58 k。我们的目标是简化内核化，同时获得改进的内核。特别是，我们研究了7个减少规则，导致一个线性核的大小为42 k+ 24。
Abstract 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.