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.

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/polyNP⊈co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.