The Complexity of Pattern Matching for $321$-Avoiding and Skew-Merged Permutations

Michael H. Albert, Marie-Louise Lackner, Martin Lackner +1

The Permutation Pattern Matching problem, asking whether a pattern permutation $\pi$ is contained in a permutation $\tau$, is known to be NP-complete. In this paper we present two polyn…