2014/06/04 by Ivan Bliznets, Bliznets, Ivan, Marek Cygan +7
Computer Science · Engineering · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #cs.CC #cs.DS #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1406.1158
openalex publication_date 2014/06/04 · arxiv created 2015/01/11 · arxiv updated 2015/01/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 \not⊆ co-NP/poly) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.