Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Parameterized Complexity of Superstring Problems
verfasst von : Ivan Bliznets, Fedor V. Fomin, Petr A. Golovach, Nikolay Karpov, Alexander S. Kulikov, Saket Saurabh
Erschienen in: Combinatorial Pattern Matching
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In the Shortest Superstring problem we are given a set of strings \(S=\{s_1, \ldots , s_n\}\) and an integer \(\ell \) and the question is to decide whether there is a superstring \(s\) of length at most \(\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)} {\text {poly}}(n)\) finds a superstring of length at most \(\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.