Advertisement
Published in:
2017 | OriginalPaper | Chapter
A 42k Kernel for the Complementary Maximal Strip Recovery Problem
Authors : Wenjun Li, Haiyan Liu, Jianxin Wang, Lingyun Xiang, Yongjie Yang
Published in: Frontiers in Algorithmics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
In the Complementary Maximal Strip Recovery problem (CMSR), we are given two strings \(S_1\) and \(S_2\) of distinct letters, where each letter 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, 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 \(74k+4\) was developed based on 8 reduction rules. Very recently, by imposing 3 new reduction rules to the previous kernelization, the linear kernel was 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}\).