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 NPcomplete. 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 gridlike decomposition into simpler building blocks. Of particular interest are the socalled 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 polynomialtime solvable if a certain graph associated with 𝒞, called the cell graph, is a forest, and it is NPcomplete otherwise. We further generalize our results to grid classes whose blocks belong to classes of bounded gridwidth. We show that the 𝒞Pattern PPM for such a grid class 𝒞 is polynomialtime solvable if the cell graph of 𝒞 avoids a cycle or a certain special type of path, and it is NPcomplete otherwise.
BibTeX  Entry
@InProceedings{jelnek_et_al:LIPIcs:2020:12718,
author = {V{\'\i}t Jel{\'\i}nek and Michal Opler and Jakub Pek{\'a}rek},
title = {{A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {52:152:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12718},
URN = {urn:nbn:de:0030drops127186},
doi = {10.4230/LIPIcs.MFCS.2020.52},
annote = {Keywords: permutations, pattern matching, grid classes}
}
Keywords: 

permutations, pattern matching, grid classes 
Collection: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 
Issue Date: 

2020 
Date of publication: 

18.08.2020 