Algorithms to check Pattern Avoidance Permutations My question is the following: Given two permutations $\pi \in S_{n}$ and $\mu \in S_{k}$, decide whether $\pi$ is $\mu$-avoiding or not.
I think the formal definition is quite hard to write in the most general fashion. Therefore, I will give the definition for the case $\mu = 132$, hopefully it will be clear for a general $\mu$ as well.
Side Note: I am writing permutations as words, i.e $\mu = 132$ means that $\mu$ is the permutation that maps $1$ to $1$, $2$ to $3$ and $3$ to $2$.
Definition: A permutation $\pi \in S_n$ is called $132$-avoiding if there does not exist integers $a_1 < a_2 < a_3$ such that $\pi(a_1) < \pi(a_3) < \pi(a_2)$. In other words, no subsequence of $\pi$ of length $3$ has its terms in the same relative order as 132.
Examples:
1- Let $\pi = 42153$. Then, $\pi$ is not $132$-avoiding since the subsequence $153$ of $\pi$ has the same relative order of $132$(i.e the smallest element is at the left hand, the largest element is the middle element and the middle element is at  the right hand.)
2- Let $\pi = 1573246$. Then, $\pi$ is not $1432$-avoiding since the subsequence $1732$ of $\pi$ has the same relative order of $1432$. However, $pi$ is $12345$-avoiding since $\pi$ has no length $5$ increasing subsequence.
Thus, the question becomes the following: Given $\pi \in S_n$ and $\mu \in S_k$, find an efficient algorithm to check whether $\pi$ is $\mu$-avoiding or not.
Obviously, one can check all $\binom{n}{k}$ subsequences of length $k$ of $\pi$ to check whether $\pi$ is $\mu$-avoiding or not. However, it is not efficient.
Side Note2: I can only come up with some simple constraints to conclude that $\pi$ is not $\mu$-avoiding such as:
1- $k$ > $n$, or
2- The number of inversions of $\mu$ is larger than $\pi$.
Thanks in advance for suggestions or(and) help.

The problem is NP complete, so no efficient algorithm (likely) exists. For a proof, see

Bose, Prosenjit, Buss, J.F., and Lubiw, A. “Pattern Matching for Permutations”. Information Processing Letters 65.5 (1998): 277–283.

You might be able to get the paper here if your institution gives you access.
