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.  1. Given a sequence S of length n, compute the shortest cubic supersequence of S, i.e., in the form of X³ and with the shortest length, where S is a subsequence of X³. We show that if |X| = n/3 + ℓ, then the problem can be solved in O(ℓ²n³) time, which beats the trivial O(n⁵) bound when ℓ = o(n).  2. For the general SCS problem with multiple input sequences, if k is the length of the optimal solution then we present an FPT algorithm running in O^∗(k^k) time.  3. Given a general SCS instance M = {S₁,...,S_m}, where S₁ is the longest among S_i’s, if the parameter is the number of positions in S₁ where one could insert letters to obtain a SCS for M, then we prove that there is no FPT algorithm parameterized on p unless P = NP.  4. Given a set of strings {S₁,...,S_m}, an integer q and an extra string T such that each S_i, 1 ≤ i ≤ m, is a subsequence of T, we show that deciding if there are k disjoint substrings of T, say T₁,T₂,...,T_k, such that ∑_j∈[k]|T_j| ≤ q, each S_i is a subsequence of some T_j, for 1 ≤ i ≤ m and 1 ≤ j ≤ k, is NP-complete. In fact, if the problem is parameterized by k, then it is even W[1]-hard. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.