Standard

Kernelization lower bound for Permutation Pattern Matching. / Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Mach, Lukáš.

In: Information Processing Letters, Vol. 115, No. 5, 05.2015, p. 527-531.

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

Harvard

Bliznets, I, Cygan, M, Komosa, P & Mach, L 2015, 'Kernelization lower bound for Permutation Pattern Matching', Information Processing Letters, vol. 115, no. 5, pp. 527-531. https://doi.org/10.1016/j.ipl.2015.01.001

APA

Bliznets, I., Cygan, M., Komosa, P., & Mach, L. (2015). Kernelization lower bound for Permutation Pattern Matching. Information Processing Letters, 115(5), 527-531. https://doi.org/10.1016/j.ipl.2015.01.001

Vancouver

Bliznets I, Cygan M, Komosa P, Mach L. Kernelization lower bound for Permutation Pattern Matching. Information Processing Letters. 2015 May;115(5):527-531. https://doi.org/10.1016/j.ipl.2015.01.001

Author

Bliznets, Ivan ; Cygan, Marek ; Komosa, Paweł ; Mach, Lukáš. / Kernelization lower bound for Permutation Pattern Matching. In: Information Processing Letters. 2015 ; Vol. 115, No. 5. pp. 527-531.

BibTeX

@article{2ce0e8609ca9480a822ac944877ead22,
title = "Kernelization lower bound for Permutation Pattern Matching",
abstract = "A permutation π contains a permutation σ as a pattern if it contains a subsequence of length |σ| whose elements are in the same relative order as in the permutation σ. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption NP⊈co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.",
keywords = "Algorithms, Parameterized complexity, Polynomial kernels",
author = "Ivan Bliznets and Marek Cygan and Pawe{\l} Komosa and Luk{\'a}{\v s} Mach",
year = "2015",
month = may,
doi = "10.1016/j.ipl.2015.01.001",
language = "English",
volume = "115",
pages = "527--531",
journal = "Information Processing Letters",
issn = "0020-0190",
publisher = "Elsevier",
number = "5",

}

RIS

TY - JOUR

T1 - Kernelization lower bound for Permutation Pattern Matching

AU - Bliznets, Ivan

AU - Cygan, Marek

AU - Komosa, Paweł

AU - Mach, Lukáš

PY - 2015/5

Y1 - 2015/5

N2 - A permutation π contains a permutation σ as a pattern if it contains a subsequence of length |σ| whose elements are in the same relative order as in the permutation σ. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption NP⊈co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.

AB - A permutation π contains a permutation σ as a pattern if it contains a subsequence of length |σ| whose elements are in the same relative order as in the permutation σ. This notion plays a major role in enumerative combinatorics. We prove that the problem does not have a polynomial kernel (under the widely believed complexity assumption NP⊈co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.

KW - Algorithms

KW - Parameterized complexity

KW - Polynomial kernels

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

U2 - 10.1016/j.ipl.2015.01.001

DO - 10.1016/j.ipl.2015.01.001

M3 - Article

AN - SCOPUS:84923233696

VL - 115

SP - 527

EP - 531

JO - Information Processing Letters

JF - Information Processing Letters

SN - 0020-0190

IS - 5

ER -

ID: 49787860