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 stacksorting (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 wellstudied problem, one whose running time is n^{k/4 + o(k)}, and a polynomialspace algorithm whose running time is the better of O(1.6181^n) and O(n^{k/2 + 1}). These results improve the earlier best bounds of n^{0.47k + o(k)} and O(1.79^n) due to Ahal and Rabinovich (2000) resp. Bruner and Lackner (2012) and are the fastest algorithms for the problem when k in Omega(log{n}). We show that both our new algorithms and the previous exponentialtime algorithms in the literature can be viewed through the unifying lens of constraintsatisfaction.
Our algorithms can also count, 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) * n^{o(k/log{k})} would contradict the exponentialtime hypothesis (ETH). For some special classes of patterns we obtain improved running times. We further prove that 3increasing and 3decreasing permutations can, in some sense, embed arbitrary permutations of almost linear length, which indicates that an algorithm with subexponential running time is unlikely, even for patterns from these restricted classes.
BibTeX  Entry
@InProceedings{berendsohn_et_al:LIPIcs:2019:11462,
author = {Benjamin Aram Berendsohn and L{\'a}szl{\'o} Kozma and D{\'a}niel Marx},
title = {{Finding and Counting Permutations via CSPs}},
booktitle = {14th International Symposium on Parameterized and Exact Computation (IPEC 2019)},
pages = {1:11:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771290},
ISSN = {18688969},
year = {2019},
volume = {148},
editor = {Bart M. P. Jansen and Jan Arne Telle},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2019/11462},
URN = {urn:nbn:de:0030drops114627},
doi = {10.4230/LIPIcs.IPEC.2019.1},
annote = {Keywords: permutations, pattern matching, constraint satisfaction, exponential time}
}
Keywords: 

permutations, pattern matching, constraint satisfaction, exponential time 
Collection: 

14th International Symposium on Parameterized and Exact Computation (IPEC 2019) 
Issue Date: 

2019 
Date of publication: 

04.12.2019 