Skip to Main content Skip to Navigation
Conference papers

Hardness of longest common subsequence for sequences with bounded run-lengths

Abstract : The longest common subsequence (LCS) problem is a classic and well-studied problem in computer science with extensive applications in diverse areas ranging from spelling error corrections to molecular biology. This paper focuses on LCS for fixed alphabet size and fixed run-lengths (i.e., maximum number of consecutive occurrences of the same symbol). We show that LCS is NP-complete even when restricted to (i) alphabets of size 3 and run-length at most 1, and (ii) alphabets of size 2 and run-length at most 2 (both results are tight). For the latter case, we show that the problem is approximable within ratio 3/5.
Complete list of metadata

Cited literature [23 references]  Display  Hide  Download
Contributor : Guillaume Blin Connect in order to contact the contributor
Submitted on : Wednesday, March 28, 2012 - 2:14:28 PM
Last modification on : Friday, September 16, 2022 - 1:49:22 PM
Long-term archiving on: : Friday, June 29, 2012 - 2:25:30 AM


Files produced by the author(s)



Guillaume Blin, Laurent Bulteau, Minghui Jiang, Pedro J. Tejada, Stéphane Vialette. Hardness of longest common subsequence for sequences with bounded run-lengths. 23rd Annual Symposium on Combinatorial Pattern Matching (CPM'12), Jul 2012, Helsinki, Finland. pp.138-148, ⟨10.1007/978-3-642-31265-6_11⟩. ⟨hal-00683311⟩



Record views


Files downloads