2026-07-21T14:17:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16142 2024-03-06T10:56:40Z ddc:004 open_access

Polynomial-Time Equivalences and Refined Algorithms for Longest Common Subsequence Variants Asahiro, Yuichi Jansson, Jesper Lin, Guohui Miyano, Eiji Ono, Hirotaka Utashima, Tadatoshi Repetition-bounded longest common subsequence problem multiset restricted longest common subsequence problem one-side-filled longest common subsequence problem two-side-filled longest common subsequence problem exact algorithms and approximation algorithms The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this paper, we study four variants of LCS: the Repetition-Bounded Longest Common Subsequence problem (RBLCS) [Yuichi Asahiro et al., 2020], the Multiset-Restricted Common Subsequence problem (MRCS) [Radu Stefan Mincu and Alexandru Popa, 2018], the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS) [Mauro Castelli et al., 2017; Mauro Castelli et al., 2019]. Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O(1.44225ⁿ)-time, dynamic programming (DP)-based algorithm for RBLCS was proposed [Yuichi Asahiro et al., 2020], where the two input sequences have lengths n and poly(n). We first establish that each of MRCS, 1FLCS, and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O(1.41422ⁿ) time, which implies that MRCS, 1FLCS, and 2FLCS can also be solved in O(1.41422ⁿ) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yuichi Asahiro and Jesper Jansson and Guohui Lin and Eiji Miyano and Hirotaka Ono and Tadatoshi Utashima 2022 Is Part Of LIPIcs, Volume 223, 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2022.15 urn:nbn:de:0030-drops-161424 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2022.15 eng https://creativecommons.org/licenses/by/4.0/legalcode