Finding small patterns in permutations in linear time

Given two permutations σ and π, the P ermutation P attern problem asks if σ is a subpattern of π. We show that the problem can be solved in time 2 O ( ℓ 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. 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 P ermutation P attern problem in linear time if a bounded-width decomposition is given in the input.

Authors

• Sylvain Guillemot
• Dániel Marx

Keywords

No keywords are indexed for this paper.