Faster Exponential Algorithm for Permutation Pattern Matching

Pawel Gawrychowski, Mateusz Rzepecki

The Permutation Pattern Matching problem asks, given two permutations $\sigma$ on $n$ elements and $\pi$, whether $\sigma$ admits a subsequence with the same relative order as $\pi$ (or, in the…