Kernelization lower bound for Permutation Pattern Matching

Ivan Bliznets, Marek Cygan, Pawel Komosa +1

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…