# Finding small patterns in permutations in linear time

arXiv: https://arxiv.org/abs/1307.3073 · HTML: https://mlsanity.com/paper/1307.3073/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jul 2013.

## Built on by (most cited first, 1 of 1)

- [Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures](https://mlsanity.com/paper/2412.08556/) (2024)

## Abstract (arXiv)

Given two permutations σ and π, the textscPermutation Pattern problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2O(ℓ2log ℓ)· n, where ℓ=|σ| and n=|π|. 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 σ as a subpattern of π, or finds a decomposition of π whose width is bounded by a function of |σ|. Then we show how to solve the textscPermutation Pattern problem in linear time if a bounded-width decomposition is given in the input.