Kernelization lower bound for permutation pattern matching

DOI10.1016/J.IPL.2015.01.001MaRDI QIDQ2339595zbMATH OpenOpenAlexFDO

Authors I. A. Bliznets, Marek Cygan, Paweł Komosa, Lukáš Mach

Publication date 2 April 2015

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.1158

zbMATH Keywords

parameterized complexitypermutation pattern matchingpolynomial kernels

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: 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 $mboxNPotsubseteqmboxco-NP/mboxpoly$) by introducing a new polynomial reduction from the clique problem to permutation pattern matching.

Recommendations

• Hardness of permutation pattern matching
• On Complexity of the Subpattern Problem
• Pattern matching for 321-avoiding permutations
• Pattern matching for permutations
• Pattern matching for permutations

Cites work

• Cross-composition: a new technique for kernelization lower bounds
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Finding pattern matchings for permutations
• Finding small patterns in permutations in linear time
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• scientific article; zbMATH DE number 1504588 (Why is no real title available?)
• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Infeasibility of instance compression and succinct PCPs for NP
• Longest Increasing and Decreasing Subsequences
• On Complexity of the Subpattern Problem
• On problems without polynomial kernels
• Pattern matching for permutations
• Restricted permutations
• Stack sortable permutations
• The computational landscape of permutation patterns

Cited in

(2)

• k-Abelian Pattern Matching
• \(k\)-abelian pattern matching

This page was built for publication: Kernelization lower bound for permutation pattern matching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339595)