Kernelization lower bound for Permutation Pattern Matching

Autor:	Bliznets, Ivan, Cygan, Marek, Komosa, Pawel, Mach, Lukas
Rok vydání:	2014
Předmět:	Computer Science - Data Structures and Algorithms Computer Science - Computational Complexity
Druh dokumentu:	Working Paper
Popis:	A permutation $\pi$ contains a permutation $\sigma$ as a pattern if it contains a subsequence of length $|\sigma|$ whose elements are in the same relative order as in the permutation $\sigma$. 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 $\mbox{NP} \not\subseteq \mbox{co-NP}/\mbox{poly}$) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1406.1158 Zobrazit plný text záznamu View this record from Arxiv