Kernelization lower bound for permutation pattern matching

DOI10.1016/j.ipl.2015.01.001zbMath1327.68114arXiv1406.1158MaRDI QIDQ2339595

Marek Cygan, Lukáš Mach, Ivan A. Bliznets, Paweł Komosa

Publication date: 2 April 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1406.1158

zbMATH Keywords

parameterized complexity; polynomial kernels; permutation pattern matching

Mathematics Subject Classification ID

05A05: Permutations, words, matrices

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)