Finding small patterns in permutations in linear time
Sylvain Guillemot, Dániel Marx · 2013
Given two permutations σ and π, the Permutation Pattern problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2O(ℓ2 log ℓ). n, where ℓ = |σ| and n = |π|. In other words, the problem is fixed-parameter tractable parameterized by the size of the subpattern to be found.