Abstract
Permutation Pattern Matching (PPM) is the problem of deciding for a given pair of permutations π and τ whether the pattern π is contained in the text τ. Bose, Buss and Lubiw showed that PPM is NP-complete.
In view of this result, it is natural to ask how the situation changes when we restrict the pattern π to a fixed permutation class 𝒞; this is known as the 𝒞-Pattern PPM problem. There have been several results in this direction, namely the work of Jelínek and Kynčl who completely resolved the hardness of 𝒞-Pattern PPM when 𝒞 is taken to be the class of σ-avoiding permutations for some σ.
Grid classes are special kind of permutation classes, consisting of permutations admitting a grid-like decomposition into simpler building blocks. Of particular interest are the so-called monotone grid classes, in which each building block is a monotone sequence.
Recently, it has been discovered that grid classes, especially the monotone ones, play a fundamental role in the understanding of the structure of general permutation classes. This motivates us to study the hardness of 𝒞-Pattern PPM for a (monotone) grid class 𝒞.
We provide a complexity dichotomy for 𝒞-Pattern PPM when 𝒞 is taken to be a monotone grid class. Specifically, we show that the problem is polynomial-time solvable if a certain graph associated with 𝒞, called the cell graph, is a forest, and it is NP-complete otherwise.
We further generalize our results to grid classes whose blocks belong to classes of bounded grid-width. We show that the 𝒞-Pattern PPM for such a grid class 𝒞 is polynomial-time solvable if the cell graph of 𝒞 avoids a cycle or a certain special type of path, and it is NP-complete otherwise.