On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems Journal Article


Author(s): Pietrzak, Krzysztof
Article Title: On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
Affiliation
Abstract: We show that the fixed alphabet shortest common supersequence (SCS) and the fixed alphabet longest common subsequence (LCS) problems parameterized in the number of strings are W[1]-hard. Unless W[1]=FPT, this rules out the existence of algorithms with time complexity of O(f(k)nα) for those problems. Here n is the size of the problem instance, α is constant, k is the number of strings and f is any function of k. The fixed alphabet version of the LCS problem is of particular interest considering the importance of sequence comparison (e.g. multiple sequence alignment) in the fixed length alphabet world of DNA and protein sequences.
Keywords: Parameterized complexity; Longest common subsequence; Shortest common supersequence; Multiple sequence alignment
Journal Title: Journal of Computer and System Sciences
Volume: 67
Issue 4
ISSN: 0022-0000
Publisher: Elsevier  
Date Published: 2003-12-01
Start Page: 757
End Page: 771
Copyright Statement: ⓒ 2003 Elsevier Inc. All rights reserved.
DOI: 10.1016/S0022-0000(03)00078-3
Open access: no
IST Austria Authors
Related IST Austria Work