论文标题
最长的子序列问题：进一步的复杂性结果
The Longest Run Subsequence Problem: Further Complexity Results
论文作者
论文摘要
最长的运行子序列是最近在基因组组装的脚手架阶段引入的问题（Schrinner等，Wabi 2020）。该问题要求给定字符串的最大长度子序列，该字符串最多包含每个符号的运行（运行是连续相同符号的最大基因）。当参数是定义输入字符串的字母大小时，该问题已被证明是NP硬化，可以进行固定参数。在本文中，我们进一步研究了问题的复杂性，并表明当它通过解决方案中的运行数（一个较小的参数）参数化时，它是固定参数可进行的。此外，我们研究了最长运行子序列的内核化复杂性，并证明当通过字母的大小或运行次数进行参数时，它不接受多项式内核。最后，当每个符号在输入字符串中最多有两个出现时，我们考虑了最长运行子序列的限制，并且我们表明它是APX-HARD。
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.
