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

K.Z. Pietrzak, Journal of Computer and System Sciences 67 (2003) 757–771.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
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.
Publishing Year
Date Published
2003-12-01
Journal Title
Journal of Computer and System Sciences
Volume
67
Issue
4
Page
757 - 771
IST-REx-ID

Cite this

Pietrzak KZ. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences. 2003;67(4):757-771. doi:10.1016/S0022-0000(03)00078-3
Pietrzak, K. Z. (2003). On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences, 67(4), 757–771. https://doi.org/10.1016/S0022-0000(03)00078-3
Pietrzak, Krzysztof Z. “On the Parameterized Complexity of the Fixed Alphabet Shortest Common Supersequence and Longest Common Subsequence Problems.” Journal of Computer and System Sciences 67, no. 4 (2003): 757–71. https://doi.org/10.1016/S0022-0000(03)00078-3.
K. Z. Pietrzak, “On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems,” Journal of Computer and System Sciences, vol. 67, no. 4, pp. 757–771, 2003.
Pietrzak KZ. 2003. On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. Journal of Computer and System Sciences. 67(4), 757–771.
Pietrzak, Krzysztof Z. “On the Parameterized Complexity of the Fixed Alphabet Shortest Common Supersequence and Longest Common Subsequence Problems.” Journal of Computer and System Sciences, vol. 67, no. 4, Elsevier, 2003, pp. 757–71, doi:10.1016/S0022-0000(03)00078-3.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar