[Back]

M. Lackner, M. Bruner:
"Permutation Pattern Matching and its Parameterized Complexity";
Talk: Conference on Computability in Europe CiE, Cambridge, Great Britain; 06-18-2012 - 06-23-2012.

The concept of pattern avoidance (and, closely related, pattern
matching) in permutations arose in the late 1960ies. It was in an
exercise of his Fundamental algorithms that Knuth asked which permutations could be sorted using a single stack. The answer is simple: These are exactly the permutations that do not contain the pattern 231. A permutation T contains a permutation P as a pattern if there exists a subsequence of T that is order-isomorphic to P. Questions regarding permutations containing (or avoiding) certain patterns have been studied intensively within the field of enumerative combinatorics.
In this talk I will take the viewpoint of computational complexity. Computational aspects of pattern avoidance, in particular the analysis of the Permutation Pattern Matching (PPM) problem, have received far less attention than enumerative questions. This problem is defined as follows: Given permutations P and T, does T contain P as a pattern? I will present first results obtained together with Marie-Louise Bruner towards a more fine-grained, parameterized complexity analysis of PPM1. We study the question how structural properties of permutations, socalled permutation statistics, influence the complexity of PPM. Permutation statistics have extensively been studied in combinatorics but their impact on computational questions regarding PPM is unexplored. In this talk I will focus on the permutation statistic "alternating runs". This statistic denotes the number of ups and downs in a permutation.
We were able to show that PPM can be solved in time O (1.79run(T)),
where run(T) denotes the number of alternating runs in T. Since run(T)
is less than n, the length of T, this algorithm also solves PPM in time O (1.79n). This is the fastest known algorithm for PPM.
I will conclude this talk by pointing out how such a parameterized
complexity analysis can shed light on the relation between permutation
statistics and computational questions concerning PPM.