A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs

作者：Bruner Marie Louise^*; Lackner Martin

来源：Algorithmica, 2016, 75(1): 84-117.

DOI：10.1007/s00453-015-0013-y

• Permutation patterns
• Parameterized complexity
• Pattern matching
• Fixed-parameter tractability
• Exponential algorithms
• Combinatorics

The NP-complete Permutation Pattern Matching problem asks whether a k-permutation P is contained in a n-permutation T as a pattern. This is the case if there exists an order-preserving embedding of P into T. In this paper, we present a fixed-parameter algorithm solving this problem with a worst-case runtime of , where denotes the number of alternating runs of T. This algorithm is particularly well-suited for instances where T has few runs, i.e., few ups and downs. Moreover, since , this can be seen as a algorithm which is the first to beat the exponential runtime of brute-force search. Furthermore, we prove that under standard complexity theoretic assumptions such a fixed-parameter tractability result is not possible for run(P).

• 出版日期2016-5