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 metadatas

Cited literature [23 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-00683311
Contributor : Guillaume Blin <>
Submitted on : Wednesday, March 28, 2012 - 2:14:28 PM
Last modification on : Wednesday, May 23, 2018 - 3:44:02 PM
Long-term archiving on : Friday, June 29, 2012 - 2:25:30 AM

File

hal.pdf
Files produced by the author(s)

Identifiers

Citation

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⟩

Share

Metrics

Record views

684

Files downloads

2594