Finding and Counting Permutations via CSPs
Benjamin Aram Berendsohn, László Kozma, Dániel Marx · Algorithmica · 2021
Abstract 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 lengthncontains a given pattern of lengthk. In this work we give two new algorithms for this well-studied problem, one whose running time is $$n^{k/4 + o(k)}$$ nk/4+o(k) , and a polynomial-space algorithm whose running time is the better of $$O(1.6181^n)$$ O(1.6181n) and $$O(n^{k/2 + 1})$$ O(nk/2+1) . These results improve the earlier best bounds of $$n^{0.47k + o(k)}$$ n0.47k+o(k) and $$O(1.79^n)$$ O(1.79n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when $$k \in \varOmega (\log {n})$$ k∈Ω(logn) . We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens ofconstraint-satisfaction. Our algorithms can alsocount, within the same running time, the number of occurrences of a pattern. We show that this result is close to optimal: solving the counting problem in time $$f(k) \cdot n^{o(k/\log {k})}$$ f(k)·no(k/logk) would contradict theexponential-time hypothesis(ETH). For some special classes of patterns we obtain improved running times. We further prove that 3-increasing(4321-avoiding) and 3-decreasing(1234-avoiding) permutations can, in some sense,embedarbitrary permutations of almost linear length, which indicates that a sub-exponential running time is unlikely with the current techniques, even for patterns from these restricted classes.