Kernelization lower bound for Permutation Pattern Matching ?
We prove that the Permutation Pattern Matching problem does not have a polynomial kernel (assuming a widely believed hypothesis from theory of computational complexity). A novel polynomial reduction from the Clique problem to the Permutation Pattern Matching problem is introduced. The standard cross-composition framework is applied to yield polynomial lower bounds.
polynomial kernels algorithms parameterized complexity