On the Existence of Parameterized Algorithms for the Shortest Common Supersequence and Related Problems
摘要
Shortest Common Supersequence (SCS) is a well-known problem in string algorithms and related applications. For multiple input sequences the problem is NP-hard and for a fixed number of d input sequences it can be solved in \(O(n^d)\) time, where n is the maximum length of the input sequences. In this paper, we consider designing parameterized algorithms or proving the non-existence of these algorithms for SCS and several of its variants.