2026-07-23T00:26:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23929 2025-11-12T13:17:26Z ddc:004 open_access

Approximability of Longest Run Subsequence and Complementary Minimization Problems Asahiro, Yuichi Gong, Mingyang Jansson, Jesper Lin, Guohui Lu, Sichen Miyano, Eiji Ono, Hirotaka Saitoh, Toshiki Tanaka, Shunichi Longest run subsequence minimum run subsequence deletion approximation algorithm We study the polynomial-time approximability of the Longest Run Subsequence problem (LRS for short) and its complementary minimization variant Minimum Run Subsequence Deletion problem (MRSD for short). For a string S = s₁ ⋯ s_n over an alphabet Σ, a subsequence S' of S is S' = s_{i₁} ⋯ s_{i_p}, such that 1 ≤ i₁ < i₂ < … < i_p ≤ |S|. A run of a symbol σ ∈ Σ in S is a maximal substring of consecutive occurrences of σ. A run subsequence S' of S is a subsequence of S in which every symbol σ ∈ Σ occurs in at most one run. The co-subsequence ̅{S'} of the subsequence S' = s_{i₁} ⋯ s_{i_p} in S is the subsequence obtained by deleting all the characters in S' from S, i.e., ̅{S'} = s_{j₁} ⋯ s_{j_{n-p}} such that j₁ < j₂ < … < j_{n-p} and {j₁, …, j_{n-p}} = {1, …, n}⧵ {i₁, …, i_p}. Given a string S, the goal of LRS (resp., MRSD) is to find a run subsequence S^* of S such that the length |S^*| is maximized (resp., the number | ̅{S^*}| of deleted symbols from S is minimized) over all the run subsequences of S. Let k be the maximum number of symbol occurrences in the input S. It is known that LRS and MRSD are APX-hard even if k = 2. In this paper, we show that LRS can be approximated in polynomial time within factors of (k+2)/3 for k = 2 or 3, and 2(k+1)/5 for every k ≥ 4. Furthermore, we show that MRSD can be approximated in linear time within a factor of (k+4)/4 if k is even and (k+3)/4 if k is odd. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuichi Asahiro and Mingyang Gong and Jesper Jansson and Guohui Lin and Sichen Lu and Eiji Miyano and Hirotaka Ono and Toshiki Saitoh and Shunichi Tanaka 2025 Is Part Of LIPIcs, Volume 344, 25th International Conference on Algorithms for Bioinformatics (WABI 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.WABI.2025.3 urn:nbn:de:0030-drops-239290 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2025.3 eng https://creativecommons.org/licenses/by/4.0/legalcode