Kernelization lower bound for permutation pattern matching

DOI10.1016/j.ipl.2015.01.001zbMath1327.68114arXiv1406.1158OpenAlexW1968201947MaRDI QIDQ2339595

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

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 complexitypolynomial kernelspermutation pattern matching

Mathematics Subject Classification ID

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding pattern matchings for permutations
• Pattern matching for permutations
• A fast algorithm for permutation pattern matching based on alternating runs
• Excluded permutation matrices and the Stanley-Wilf conjecture
• Infeasibility of instance compression and succinct PCPs for NP
• On problems without polynomial kernels
• Stack sortable permutations
• The computational landscape of permutation patterns
• Longest Increasing and Decreasing Subsequences
• On Complexity of the Subpattern Problem
• Finding small patterns in permutations in linear time
• Restricted permutations

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