Faster and simpler algorithms for finding large patterns in permutations

02/23/2019
by   László Kozma, et al.
0

Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of Knuth on stack-sorting (1968). Perhaps the most natural algorithmic question in this area is deciding whether a given permutation of length n contains a given pattern of length k. In this work we give two new algorithms for this well-studied problem, one whose running time is n^0.44k+o(k), and one whose running time is the better of O(1.415^n) and n^k/2+o(k). These results improve the earlier best bounds of Ahal and Rabinovich (2000), and Bruner and Lackner (2012), and are the fastest algorithms for the problem when k = Ω( n). When k = o( n), the parameterized algorithm of Guillemot and Marx (2013) dominates. Our second algorithm uses polynomial space and is significantly simpler than all previous approaches with comparable running times, including an n^k/2+o(k) algorithm proposed by Guillemot and Marx. Our approach can be summarized as follows: "for every matching of the even-valued entries of the pattern, try to match all odd-valued entries left-to-right". For the special case of patterns that are Jordan-permutations, we show an improved, subexponential running time.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset