×

An improved linear kernel for complementary maximal strip recovery: simpler and smaller. (English) Zbl 1429.68340

Summary: 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\).

MSC:

68W32 Algorithms on strings
68Q27 Parameterized complexity, tractability and kernelization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aghighi, M.; Bäckström, C., Plan reordering and parallel execution – a parameterized complexity view, (AAAI (2017)), 3540-3546
[2] Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hallett, M. T.; Wareham, H. T., Parameterized complexity analysis in computational biology, Comput. Appl. Biosci., 11, 1, 49-57 (1995)
[3] Bulteau, L.; Fertin, G.; Jiang, M.; Rusu, I., Tractability and approximability of maximal strip recovery, Theoret. Comput. Sci., 440-441, 14-28 (2012) · Zbl 1252.68349
[4] Bulteau, L.; Fertin, G.; Rusu, I., Maximal strip recovery problem with gaps: hardness and approximation algorithms, J. Discrete Algorithms, 19, 1-22 (2013) · Zbl 1280.68094
[5] Chen, Z.; Fu, B.; Jiang, M.; Zhu, B., On recovering syntenic blocks from comparative maps, J. Comb. Optim., 18, 3, 307-318 (2009) · Zbl 1180.90261
[6] Choi, V.; Zheng, C.; Zhu, Q.; Sankoff, D., Algorithms for the extraction of synteny blocks from comparative maps, (WABI (2007)), 277-288
[7] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness I: basic results, SIAM J. Comput., 24, 4, 873-921 (1995) · Zbl 0830.68063
[8] Downey, R. G.; Fellows, M. R., Fixed-parameter tractability and completeness II: on completeness for W[1], Theoret. Comput. Sci., 141, 1-2, 109-131 (1995) · Zbl 0873.68059
[9] Downey, R. G.; Fellows, M. R., Fundamentals of Parameterized Complexity, Texts in Computer Science (2013), Springer · Zbl 1358.68006
[10] Q. Feng, N. Huang, X. Jiang, J. Wang, Dealing with several parameterized problems by random methods, Theor. Comput. Sci. Available online 28 September 2017.; Q. Feng, N. Huang, X. Jiang, J. Wang, Dealing with several parameterized problems by random methods, Theor. Comput. Sci. Available online 28 September 2017. · Zbl 1393.68131
[11] Hu, S.; Li, W.; Wang, J., An improved kernel for the complementary maximal strip recovery problem, (COCOON (2015)), 601-608 · Zbl 1465.68113
[12] Jiang, H.; Li, Z.; Lin, G.; Wang, L.; Zhu, B., Exact and approximation algorithms for the complementary maximal strip recovery problem, J. Comb. Optim., 23, 4, 493-506 (2012) · Zbl 1245.90105
[13] Jiang, H.; Zhu, B., A linear kernel for the complementary maximal strip recovery problem, J. Comput. System Sci., 80, 7, 1350-1358 (2014) · Zbl 1311.68205
[14] Jiang, M., Inapproximability of maximal strip recovery, Theoret. Comput. Sci., 412, 29, 3759-3774 (2011) · Zbl 1217.92041
[15] Kowalik, L.; Pilipczuk, M.; Suchan, K., Towards optimal kernel for connected vertex cover in planar graphs, Discrete Appl. Math., 161, 7-8, 1154-1161 (2013) · Zbl 1263.05021
[16] Li, W.; Feng, Q.; Chen, J.; Hu, S., Improved kernel results for some FPT problems based on simple observations, Theoret. Comput. Sci., 657, 20-27 (2017) · Zbl 1356.68102
[17] Li, W.; Liu, H.; Wang, J.; Xiang, L.; Yang, Y., A \(42k\) kernel for the complementary maximal strip recovery problem, (FAW (2017)), 175-186 · Zbl 1429.68339
[18] Lin, G.; Goebel, R.; Li, Z.; Wang, L., An improved approximation algorithm for the complementary maximal strip recovery problem, J. Comput. System Sci., 78, 3, 720-730 (2012) · Zbl 1244.68087
[19] Lin, M.; Feng, Q.; Chen, J.; Li, W., Partition on trees with supply and demand: kernelization and algorithms, Theoret. Comput. Sci., 657, 11-19 (2017) · Zbl 1356.68104
[20] Niedermeier, R., Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press Inc. · Zbl 1095.68038
[21] Wang, J.; Yang, Y.; Guo, J.; Chen, J., Planar graph vertex partition for linear problem kernels, J. Comput. System Sci., 79, 5, 609-621 (2013) · Zbl 1268.68136
[22] Wang, L.; Zhu, B., On the tractability of maximal strip recovery, J. Comput. Biol., 17, 7, 907-914 (2010)
[23] Yang, Y., Towards optimal kernel for edge-disjoint triangle packing, Inform. Process. Lett., 114, 7, 344-348 (2014) · Zbl 1284.68285
[24] Yang, Y.; Guo, J., Controlling elections with bounded single-peaked width, (AAMAS (2014)), 629-636
[25] Yang, Y.; Wang, J., Anyone but them: the complexity challenge for a resolute election controller, (AAMAS (2017)), 1133-1141
[26] Zheng, C., Pathgroups, a dynamic data structure for genome reconstruction problems, Bioinformatics, 26, 13, 1587-1594 (2010)
[28] Zheng, C.; Zhu, Q.; Sankoff, D., Removing noise and ambiguities from comparative maps in rearrangement analysis, IEEE/ACM Trans. Comput. Biol. Bioinform., 4, 4, 515-522 (2007)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.