ICE-TCS seminar: Michal Opler
Solving hard problems effectively on permutations of small grid-width
ICE-TCS seminar #344
Date and time: Monday, 18 November 2019, 11:50-12:35
Location: Room M106
Speaker: Michal Opler
Title: Solving hard problems effectively on permutations of small grid-width
Abstract: From a computer scientist’s point of view, the natural question to ask about permutations is, given permutations p and s, whether p is contained in s. It has been shown by Bose, Buss and Lubiw that this problem, called permutation pattern matching, is NP-complete and there has been a substantial amount of results determining the tractability of its various restricted versions.
In this seminar, we present results that connect the tractability of permutation pattern matching with the structure of permutations p and s. In particular, we introduce a grid-like decomposition of permutations and a corresponding parameter called grid-width, which are well-suited for designing dynamic programming algorithms on permutations. Our main algorithmic contribution is a polynomial time algorithm for computing the longest common subpattern of two permutations given that one of them has bounded grid-width.
We also investigate which permutation classes have bounded grid-width and thus allow for pattern matching in polynomial time.
This is joint work with Vít Jelínek.
