LIPIcs.CPM.2021.14.pdf
- Filesize: 0.82 MB
- 15 pages
Document
The Longest Run Subsequence Problem: Further Complexity Results
Authors
Riccardo Dondi 
,
Florian Sikora
-
Part of:
Volume:
32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Annual Symposium on Combinatorial Pattern Matching (CPM) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2021-06-30
File
Document Identifiers
Author Details
Cite AsGet BibTex
Riccardo Dondi and Florian Sikora. The Longest Run Subsequence Problem: Further Complexity Results. In 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 191, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.CPM.2021.14
https://doi.org/10.4230/LIPIcs.CPM.2021.14
Abstract
Longest Run Subsequence is a problem introduced recently in the context of the scaffolding phase of genome assembly (Schrinner et al., WABI 2020). The problem asks for a maximum length subsequence of a given string that contains at most one run for each symbol (a run is a maximum substring of consecutive identical symbols). The problem has been shown to be NP-hard and to be fixed-parameter tractable when the parameter is the size of the alphabet on which the input string is defined. In this paper we further investigate the complexity of the problem and we show that it is fixed-parameter tractable when it is parameterized by the number of runs in a solution, a smaller parameter. Moreover, we investigate the kernelization complexity of Longest Run Subsequence and we prove that it does not admit a polynomial kernel when parameterized by the size of the alphabet or by the number of runs. Finally, we consider the restriction of Longest Run Subsequence when each symbol has at most two occurrences in the input string and we show that it is APX-hard.
Subject Classification
ACM Subject Classification
- Theory of computation → Fixed parameter tractability
- Theory of computation → Approximation algorithms analysis
- Theory of computation → Graph algorithms analysis
Keywords
- Parameterized complexity
- Kernelization
- Approximation Hardness
- Longest Subsequence
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Paola Alimonti and Viggo Kann. Some APX-completeness results for cubic graphs. Theor. Comput. Sci., 237(1-2):123-134, 2000. URL: https://doi.org/10.1016/S0304-3975(98)00158-3.
- Michael Alonge, Sebastian Soyk, Srividya Ramakrishnan, Xingang Wang, Sara Goodwin, Fritz J. Sedlazeck, Zachary B Lippman, and Michael C. Schatz. Fast and accurate reference-guided scaffolding of draft genomes. Genome Biology, 20:244, 2019. URL: https://doi.org/10.1101/519637.
- Alberto Apostolico, Gad M. Landau, and Steven Skiena. Matching for run-length encoded strings. J. Complex., 15(1):4-16, 1999. URL: https://doi.org/10.1006/jcom.1998.0493.
-
Hans L. Bodlaender, Bart M. P. Jansen, and Stefan Kratsch. Kernelization Lower Bounds by Cross-Composition. SIAM J. Discrete Math., 28(1):277-305, 2014.
- Lauren Coombe, Vladimir Nikolic, Justin Chu, Inanc Birol, and René Warren. ntJoin: Fast and lightweight assembly-guided scaffolding using minimizer graphs. Bioinformatics, 36:3885–3887, 2020. URL: https://doi.org/10.1093/bioinformatics/btaa253.
-
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015.
- Manish Goel, Hequan Sun, Wen-Biao Jiao, and Korbinian Schneeberger. SyRI: finding genomic rearrangements and local sequence differences from whole-genome assemblies. Genome Biology, 20:277, 2019. URL: https://doi.org/10.1186/s13059-019-1911-0.
- Ioannis Koutis. Faster Algebraic Algorithms for Path and Packing Problems. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, volume 5125 of LNCS, pages 575-586. Springer, 2008. URL: https://doi.org/10.1007/978-3-540-70575-8_47.
- Christos H. Papadimitriou and Mihalis Yannakakis. Optimization, Approximation, and Complexity Classes. J. Comput. Syst. Sci., 43(3):425-440, 1991. URL: https://doi.org/10.1016/0022-0000(91)90023-X.
- Sven Schrinner, Manish Goel, Michael Wulfert, Philipp Spohr, Korbinian Schneeberger, and Gunnar W. Klau. The longest run subsequence problem. In Carl Kingsford and Nadia Pisanti, editors, 20th International Workshop on Algorithms in Bioinformatics, WABI 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 172 of LIPIcs, pages 6:1-6:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.WABI.2020.6.
- Ryan Williams. Finding paths of length k in O^*(2^k) time. Inf. Process. Lett., 109(6):315-318, 2009. URL: https://doi.org/10.1016/j.ipl.2008.11.004.