2026-07-24T21:22:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12718 2024-03-06T10:50:40Z ddc:004 open_access

A Complexity Dichotomy for Permutation Pattern Matching on Grid Classes Jelínek, Vít Opler, Michal Pekárek, Jakub permutations pattern matching grid classes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vít Jelínek and Michal Opler and Jakub Pekárek 2020 Is Part Of LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2020.52 urn:nbn:de:0030-drops-127186 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.52 eng https://creativecommons.org/licenses/by/3.0/legalcode