Parameterized Complexity of Superstring Problems

In the Shortest Superstring problem we are given a set of strings $S={s_1, \ldots, s_n}$andinteger$\ell$ and the question is to decide whether there is a superstring $s$ of length at most $\mathrm{\ell }$ containing all strings of $S$ as substrings. We obtain several parameterized algorithms and complexity results for this problem. In particular, we give an algorithm which in time $2^{O(k)} \operatorname{poly}(n)$findsasuperstringoflengthatmost$\ell$ containing at least $k$ strings of $S$. We complement this by the lower bound showing that such a parameterization does not admit a polynomial kernel up to some complexity assumption. We also obtain several results about “below guaranteed values” parameterization of the problem. We show that parameterization by compression admits a polynomial kernel while parameterization “below matching” is hard.