 |
Parity Permutation Pattern Matching
1 : Laboratoire dánalyse et modélisation de systèmes pour láide à la décision
Centre National de la Recherche Scientifique : UMR7243 / FRE3234 / UMR7024, Université Paris Dauphine-PSL, Centre National de la Recherche Scientifique : UMR7024, Centre National de la Recherche Scientifique
2 : Laboratoire dÍnformatique Gaspard-Monge
Ecole des Ponts ParisTech, Centre National de la Recherche Scientifique, Université Gustave Eiffel, Centre National de la Recherche Scientifique : UMR8049
Given two permutations, a pattern σ and a text π, Parity Permutation Pattern Matching asks whether there exists a parity and order preserving embedding of σ into π.
While it is known that Permutation Pattern Matching is in FPT, we show that adding the parity constraint to the problem makes it W[1]-hard, even for alternating permutations or for 4321-avoiding patterns. However, it remains in FPT if the text 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 both permutations are separable, or if both are 321-avoiding, but NP-hard if the pattern is 321-avoiding and the text is 4321-avoiding.
