Hardness of permutation pattern matching

DOI10.1137/1.9781611974782.24MaRDI QIDQ4575761zbMATH OpenOpenAlexFDO

Authors Vít Jelínek, Jan Kynčl

Publication date 16 July 2018

Published in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorics in computer science (68R05)

Abstract: Permutation Pattern Matching (or PPM) is a decision problem whose input is a pair of permutations $pi$ and $au$, represented as sequences of integers, and the task is to determine whether $au$ contains a subsequence order-isomorphic to $pi$. Bose, Buss and Lubiw proved that PPM is NP-complete on general inputs. We show that PPM is NP-complete even when $pi$ has no decreasing subsequence of length 3 and $au$ has no decreasing subsequence of length 4. This provides the first known example of PPM being hard when one or both of $pi$ and $sigma$ are restricted to a proper hereditary class of permutations. This hardness result is tight in the sense that PPM is known to be polynomial when both $pi$ and $au$ avoid a decreasing subsequence of length 3, as well as when $pi$ avoids a decreasing subsequence of length 2. The result is also tight in another sense: we will show that for any hereditary proper subclass C of the class of permutations avoiding a decreasing sequence of length 3, there is a polynomial algorithm solving PPM instances where $pi$ is from C and $au$ is arbitrary. We also obtain analogous hardness and tractability results for the class of so-called skew-merged patterns. From these results, we deduce a complexity dichotomy for the PPM problem restricted to $pi$ belonging to $Av(ho)$, where $Av(ho)$ denotes the class of permutations avoiding a permutation $ho$. Specifically, we show that the problem is polynomial when $ho$ is in the set {1, 12, 21, 132, 213, 231, 312}, and it is NP-complete for any other $ho$.

Recommendations

• The complexity of pattern matching for 321-avoiding and skew-merged permutations
• Pattern matching for 321-avoiding permutations
• Pattern matching for permutations
• Pattern matching for permutations
• On Complexity of the Subpattern Problem

Cited in

(15)

• Finding and counting permutations via CSPs
• Kernelization lower bound for permutation pattern matching
• Finding pattern matchings for permutations
• The computational landscape of permutation patterns
• On Complexity of the Subpattern Problem
• Pattern matching for 321-avoiding permutations
• The complexity of pattern matching for 321-avoiding and skew-merged permutations
• Generalized Coloring of Permutations
• Pattern matching for permutations
• scientific article; zbMATH DE number 7559423 (Why is no real title available?)
• Combinatorial generation via permutation languages. I: Fundamentals
• scientific article; zbMATH DE number 7765381 (Why is no real title available?)
• Parity permutation pattern matching
• Generalized coloring of permutations
• Parity permutation pattern matching

This page was built for publication: Hardness of permutation pattern matching

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