摘要：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 ð'Z; this is known as the ð'Z-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 ð'Z-Pattern PPM when ð'Z is taken to be the class of Ïf-avoiding permutations for some Ïf. 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 ð'Z-Pattern PPM for a (monotone) grid class ð'Z. We provide a complexity dichotomy for ð'Z-Pattern PPM when ð'Z is taken to be a monotone grid class. Specifically, we show that the problem is polynomial-time solvable if a certain graph associated with ð'Z, 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 ð'Z-Pattern PPM for such a grid class ð'Z is polynomial-time solvable if the cell graph of ð'Z avoids a cycle or a certain special type of path, and it is NP-complete otherwise.
