On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems. (English) Zbl 1092.68049
Summary: 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^{\alpha}\)) for those problems. Here \(n\) is the size of the problem instance, \(\alpha\) 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.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
Keywords:
Parameterized complexity; Longest common subsequence; Shortest common supersequence; Multiple sequence alignmentReferences:
| [1] | Aho, A. V.; Hirschberg, D. S.; Ullman, J. D., Bounds on the complexity of the longest common subsequence problem, J. Assoc. Comput. Mach., 23, 1, 1-12 (1976) · Zbl 0316.68027 |
| [2] | Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Hallett, M. T.; Wareham, H. T., Parameterized complexity analysis in computational biology, CABIOS, 11, 1, 49-57 (1995) |
| [3] | Bodlaender, H. L.; Downey, R. G.; Fellows, M. R.; Wareham, H. T., The parameterized complexity of sequence alignment and consensus, Theoret. Comput. Sci., 147, 31-54 (1994) · Zbl 0888.68060 |
| [4] | Downey, R. G.; Fellows, M. R., Parameterized Complexity, Monographs in Computer Science (1999), Springer: Springer Berlin · Zbl 0914.68076 |
| [5] | K. Hakata, H. Imai, The longest common subsequence problem for small alphabet size between many strings. Proceedings of the third Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 670, Springer, Berlin, 1992.; K. Hakata, H. Imai, The longest common subsequence problem for small alphabet size between many strings. Proceedings of the third Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 670, Springer, Berlin, 1992. · Zbl 0947.90121 |
| [6] | M.T. Hallett, An integrated complexity analysis of problems from computational biology, Ph.D. Dissertation, University of Victoria, 1996.; M.T. Hallett, An integrated complexity analysis of problems from computational biology, Ph.D. Dissertation, University of Victoria, 1996. |
| [7] | R.W. Irving, C.B. Fraser, Two algorithms for the longest common subsequence of three (or more) strings, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, Vol. 644, Springer, Berlin, 1992, pp. 214-229.; R.W. Irving, C.B. Fraser, Two algorithms for the longest common subsequence of three (or more) strings, Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching (CPM), Lecture Notes in Computer Science, Vol. 644, Springer, Berlin, 1992, pp. 214-229. |
| [8] | Maier, D., The complexity of some problems on subsequences and supersequences, J. Assoc. Comput. Mach., 25, 2, 322-336 (1978) · Zbl 0371.68018 |
| [9] | Räihä, K. J.; Ukkonen, E., The shortest common supersequence problem over a binary alphabet is \(NP\)-complete, Theoret. Comput. Sci., 16, 187-198 (1981) · Zbl 0469.68049 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
