The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2021.14
URN: urn:nbn:de:0030-drops-139652
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/13965/
Go to the corresponding LIPIcs Volume Portal

Dondi, Riccardo ; Sikora, Florian

The Longest Run Subsequence Problem: Further Complexity Results

pdf-format:
LIPIcs-CPM-2021-14.pdf (0.8 MB)

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.

BibTeX - Entry

@InProceedings{dondi_et_al:LIPIcs.CPM.2021.14,
  author =	{Dondi, Riccardo and Sikora, Florian},
  title =	{{The Longest Run Subsequence Problem: Further Complexity Results}},
  booktitle =	{32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)},
  pages =	{14:1--14:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-186-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{191},
  editor =	{Gawrychowski, Pawe{\l} and Starikovskaya, Tatiana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/13965},
  URN =		{urn:nbn:de:0030-drops-139652},
  doi =		{10.4230/LIPIcs.CPM.2021.14},
  annote =	{Keywords: Parameterized complexity, Kernelization, Approximation Hardness, Longest Subsequence}
}

Keywords: Parameterized complexity, Kernelization, Approximation Hardness, Longest Subsequence
Collection: 32nd Annual Symposium on Combinatorial Pattern Matching (CPM 2021)
Issue Date: 2021
Date of publication: 30.06.2021

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI