# On the Parameterized Complexity of the Fixed Alphabet Shortest Common Supersequence and Longest Common Subsequence Problems

## Krzysztof Pietrzak

```
```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^c)
for those problems.
Here n is the size of the problem instance, c 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.