Finding small patterns in permutations in linear time

2013/07/11 by Sylvain Guillemot, Dániel Marx, Guillemot, Sylvain +1 · 6 citations
Computer Science · Engineering · #Algorithms and Data Compression #Cellular Automata and Applications #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #cs.DS #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1307.3073

openalex publication_date 2013/07/11 · arxiv created 2013/10/31 · arxiv updated 2013/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Cited by

• First-Order Logic and Twin-Width for Some Geometric Graphs
• Compact representations of pattern-avoiding permutations
• Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
• Permutation patterns in streams
• Finding Order-Preserving Subgraphs
• A Polynomial-Time Approximation Algorithm for Complete Interval Minors

Related

• Griddings of permutations and hardness of pattern matching
• Faster and simpler algorithms for finding large patterns in permutations
• Finding and counting permutations via CSPs
• Fast Algorithms for Finding Pattern Avoiders and Counting Pattern\n Occurrences in Permutations
• Long paths make pattern-counting hard, and deep trees make it harder