Parity Permutation Pattern Matching

Given two permutations, a pattern \(\sigma \) $\sigma$ and a text \(\pi \) $\pi$ , Parity Permutation Pattern Matching asks whether there exists a parity and order preserving embedding of \(\sigma \) $\sigma$ into \(\pi \) $\pi$ . While it is known that Permutation Pattern Matching is in \(\textsc {FPT}\) $\mathrm{FPT}$ , we show that adding the parity constraint to the problem makes it \(\textsc {W}[1]\) $\mathrm{W}[1]$ -hard, even for alternating permutations or for 4321-avoiding patterns. However, the problem remains in \(\textsc {FPT}\) $\mathrm{FPT}$ if \(\pi \) $\pi$ avoids a fixed permutation, thanks to a recent meta-theorem on twin-width. On the other hand, as for the classical version, Parity Permutation Pattern Matching remains polynomial-time solvable when the pattern is separable, or if both permutations are 321-avoiding, but NP-hard if \(\sigma \) $\sigma$ is 321-avoiding and \(\pi \) $\pi$ is 4321-avoiding.