2012/04/23 by Marie-Louise Bruner, Bruner, Marie-Louise, Martin Lackner +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Algorithms and Data Compression #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Genome Rearrangement Algorithms #cs.CC #cs.DS #graph theory and CDMA systems #math.CO #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1204.5224
openalex publication_date 2012/04/23 · arxiv created 2015/03/16 · arxiv updated 2015/03/17 · openalex created_date 2022/09/28 · openalex updated_date 2026/07/28
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 O(1.79run(T)⋅ n⋅ k), where run(T) 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 run(T)<n, this can be seen as a O(1.79n⋅ n⋅ k) algorithm which is the first to beat the exponential 2n 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).