Standard

Parameterized Complexity of Superstring Problems. / Bliznets, Ivan; Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.; Saurabh, Saket.

In: Algorithmica, Vol. 79, No. 3, 01.11.2017, p. 798-813.

Research output: Contribution to journal › Article › peer-review

Harvard

Bliznets, I, Fomin, FV, Golovach, PA, Karpov, N, Kulikov, AS & Saurabh, S 2017, 'Parameterized Complexity of Superstring Problems', Algorithmica, vol. 79, no. 3, pp. 798-813. https://doi.org/10.1007/s00453-016-0193-0

APA

Bliznets, I., Fomin, F. V., Golovach, P. A., Karpov, N., Kulikov, A. S., & Saurabh, S. (2017). Parameterized Complexity of Superstring Problems. Algorithmica, 79(3), 798-813. https://doi.org/10.1007/s00453-016-0193-0

Vancouver

Bliznets I, Fomin FV, Golovach PA, Karpov N, Kulikov AS, Saurabh S. Parameterized Complexity of Superstring Problems. Algorithmica. 2017 Nov 1;79(3):798-813. https://doi.org/10.1007/s00453-016-0193-0

Author

Bliznets, Ivan ; Fomin, Fedor V. ; Golovach, Petr A. ; Karpov, Nikolay ; Kulikov, Alexander S. ; Saurabh, Saket. / Parameterized Complexity of Superstring Problems. In: Algorithmica. 2017 ; Vol. 79, No. 3. pp. 798-813.

BibTeX

@article{8fb4a5da7831439e99a08f69025040e6,
title = "Parameterized Complexity of Superstring Problems",
abstract = "In the Shortest Superstring problem we are given a set of strings S= { s1, … , sn} and integer ℓ and the question is to decide whether there is a superstring s of length at most ℓ 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 )poly (n) finds a superstring of length at most ℓ 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 = "Kernelization, Parameterized complexity, Shortest superstring",
author = "Ivan Bliznets and Fomin, {Fedor V.} and Golovach, {Petr A.} and Nikolay Karpov and Kulikov, {Alexander S.} and Saket Saurabh",
year = "2017",
month = nov,
day = "1",
doi = "10.1007/s00453-016-0193-0",
language = "English",
volume = "79",
pages = "798--813",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer Nature",
number = "3",

}

RIS

TY - JOUR

T1 - Parameterized Complexity of Superstring Problems

AU - Bliznets, Ivan

AU - Fomin, Fedor V.

AU - Golovach, Petr A.

AU - Karpov, Nikolay

AU - Kulikov, Alexander S.

AU - Saurabh, Saket

PY - 2017/11/1

Y1 - 2017/11/1

N2 - In the Shortest Superstring problem we are given a set of strings S= { s1, … , sn} and integer ℓ and the question is to decide whether there is a superstring s of length at most ℓ 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 )poly (n) finds a superstring of length at most ℓ 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.

AB - In the Shortest Superstring problem we are given a set of strings S= { s1, … , sn} and integer ℓ and the question is to decide whether there is a superstring s of length at most ℓ 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 )poly (n) finds a superstring of length at most ℓ 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.

KW - Kernelization

KW - Parameterized complexity

KW - Shortest superstring

UR - http://www.scopus.com/inward/record.url?scp=84979980602&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0193-0

DO - 10.1007/s00453-016-0193-0

M3 - Article

AN - SCOPUS:84979980602

VL - 79

SP - 798

EP - 813

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 3

ER -

ID: 49820985