Parameterized Complexity of Superstring Problems

Algorithmica. 2017. Vol. 79. No. 3. P. 798–813.

Bliznets Ivan, Fomin F., Golovach P., Karpov N., Kulikov A., Saurabh S.

In the Shortest Superstring problem we are given a set of strings S=\{s_1, \ldots , s_n\} and integer \ell and the question is to decide whether there is a superstring s of length at most \ellcontaining 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^{\mathcal {O}(k)} {\text {poly}}(n) finds a superstring of length at most \ell containing at least k strings of S. We complement this by a 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.

Keywords: алгоритм, algorithm, parameterized complexity, superstring, параметризованная сложность, надстрока