Kernelization lower bound for Permutation Pattern Matching
2014
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
11
References
0
Citations
NaN
KQI