Finding small patterns in permutations in linear time

Abstract

Given two permutations $\sigma$ and $\pi$, the \textsc{Permutation Pattern} problem asks if $\sigma$ is a subpattern of $\pi$. We show that the problem can be solved in time $2^{O({\ell }^2\log \ell )}\cdot n$, where $\ell =|\sigma |$ and $n=|\pi |$. In other words, the problem is fixed-parameter tractable parameterized by the size of the subpattern to be found. We introduce a novel type of decompositions for permutations and a corresponding width measure. We present a linear-time algorithm that either finds $\sigma$ as a subpattern of $\pi$, or finds a decomposition of $\pi$ whose width is bounded by a function of $|\sigma |$. Then we show how to solve the \textsc{Permutation Pattern} problem in linear time if a bounded-width decomposition is given in the input.