×

Finding and counting permutations via CSPs. (English) Zbl 1515.68216

Summary: Permutation patterns and pattern avoidance have been intensively studied in combinatorics and computer science, going back at least to the seminal work of D. E. Knuth on stack-sorting [The art of computer programming. Vol. 1: Fundamental algorithms. London: Addison-Wesley Publishing Company (1968; Zbl 0191.17903)]. 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^{k/4 + o(k)}\), and a polynomial-space 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 S. Ahal and Y. Rabinovich [SIAM J. Discrete Math. 22, No. 2, 629–649 (2008; Zbl 1164.68028)] resp. M.-L. Bruner and M. Lackner [PU.M.A., Pure Math. Appl. 24, No. 2, 83–101 (2013; Zbl 1313.05003)] and are the fastest algorithms for the problem when \(k \in \varOmega (\log{n})\). We show that both our new algorithms and the previous exponential-time algorithms in the literature can be viewed through the unifying lens of constraint-satisfaction. 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) \cdot n^{o(k/\log{k})}\) would contradict the exponential-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, embed arbitrary 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.

MSC:

68R05 Combinatorics in computer science
05A05 Permutations, words, matrices
68P10 Searching and sorting
68W05 Nonnumerical algorithms
68W40 Analysis of algorithms

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

Online Encyclopedia of Integer Sequences:

a(n) = max{ C(n,0), C(n-1,1), C(n-2,2), ..., C(n-n,n) }.

References:

[1] Ahal, S.; Rabinovich, Y., On complexity of the subpattern problem, SIAM J. Discrete Math., 22, 2, 629-649 (2008) · Zbl 1164.68028 · doi:10.1137/S0895480104444776
[2] Albert, MH; Paterson, MS, Bounds for the growth rate of meander numbers, J. Comb. Theory Ser. A, 112, 2, 250-262 (2005) · Zbl 1076.05001 · doi:10.1016/j.jcta.2005.02.006
[3] Albert, M.; Bousquet-Mélou, M., Permutations sortable by two stacks in parallel and quarter plane walks, Eur. J. Comb., 43, 131-164 (2015) · Zbl 1301.05005 · doi:10.1016/j.ejc.2014.08.024
[4] Albert, M.H., Aldred, R.E.L., Atkinson, M.D., Holton, D.A.: Algorithms for pattern involvement in permutations. In: Proceedings of the 12th International Symposium on Algorithms and Computation, ISAAC ’01, pp. 355-366, Springer-Verlag, London, UK (2001) · Zbl 1077.68720
[5] Albert, MH; Homberger, C.; Pantone, J.; Shar, N.; Vatter, V., Generating permutations with restricted containers, J. Comb. Theory Ser. A, 157, 205-232 (2018) · Zbl 1385.05002 · doi:10.1016/j.jcta.2018.02.006
[6] Albert, MH; Lackner, ML; Lackner, M.; Vatter, V., The complexity of pattern matching for 321-avoiding and skew-merged permutations, Discrete Math. Theor. Comput. Sci., 18, 2, 1-17 (2016) · Zbl 1400.05003
[7] Aldous, D.; Diaconis, P., Longest increasing subsequences: from patience sorting to the baik-deift-johansson theorem, Bull. Am. Math. Soc, 36, 413-432 (1999) · Zbl 0937.60001 · doi:10.1090/S0273-0979-99-00796-X
[8] Arthur, D.: Fast sorting and pattern-avoiding permutations. In: Proceedings of the Fourth Workshop on Analytic Algorithmics and Combinatorics, ANALCO 2007, pp. 169-174 (2007) · Zbl 1429.68051
[9] Ben-Eliezer, O., Canonne, C.L.: Improved bounds for testing forbidden order patterns. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pp. 2093-2112 (2018) · Zbl 1403.68327
[10] Berendsohn, B.A.: Complexity of permutation pattern matching. Master’s thesis, Freie Universität Berlin, (2019)
[11] Berndt, D.J., Clifford, J.: Using dynamic time warping to find patterns in time series. In: Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. AAAIWS’94, pp. 359-370. AAAI Press, (1994)
[12] Bodlaender, HL, A partial k-arboretum of graphs with bounded treewidth, Theor. Comput. Sci., 209, 1, 1-45 (1998) · Zbl 0912.68148 · doi:10.1016/S0304-3975(97)00228-4
[13] Bóna, M., A survey of stack-sorting disciplines, Electron. J. Comb., 9, 2, 1 (2003) · Zbl 1028.05003 · doi:10.37236/1693
[14] Bóna, M., Combinatorics of Permutations (2004), Boca Raton, FL, USA: CRC Press Inc, Boca Raton, FL, USA · Zbl 1052.05001 · doi:10.1201/9780203494370
[15] Bóna, M., A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory (2011), Singapore: World Scientific, Singapore · Zbl 1236.05001 · doi:10.1142/8027
[16] Bose, Pt; Buss, JF; Lubiw, A., Pattern matching for permutations, Inf. Process. Lett., 65, 5, 277-283 (1998) · Zbl 1338.68304 · doi:10.1016/S0020-0190(97)00209-3
[17] Bringmann, K., Kozma, L., Moran, S., Narayanaswamy, N.S.: Hitting set for hypergraphs of low vc-dimension. In: 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, pp. 23:1-23:18, Aarhus, Denmark (2016) · Zbl 1397.68092
[18] Bruner, M-L; Lackner, M., The computational landscape of permutation patterns, Pure Math. Appl., 24, 2, 83-101 (2013) · Zbl 1313.05003
[19] Bruner, M-L; Lackner, M., A fast algorithm for permutation pattern matching based on alternating runs, Algorithmica, 75, 1, 84-117 (2016) · Zbl 1344.68311 · doi:10.1007/s00453-015-0013-y
[20] Bulteau, L.; Rizzi, R.; Vialette, S.; Iliopoulos, C.; Leong, HW; Sung, W-K, Pattern matching for k-track permutations, Combinatorial Algorithms, 102-114 (2018), Cham: Springer International Publishing, Cham · Zbl 1511.68191 · doi:10.1007/978-3-319-94667-2_9
[21] Chalermsook, P., Goswami, M., Kozma, L., Mehlhorn, K., Saranurak, T.: Pattern-avoiding access in binary search trees. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp. 410-423, 2015 · Zbl 1466.68032
[22] Chang, M-S; Wang, F-H, Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs, Inf. Process. Lett., 43, 6, 293-295 (1992) · Zbl 0768.68126 · doi:10.1016/0020-0190(92)90114-B
[23] Chen, Hubie, A rendezvous of logic, complexity, and algebra, ACM Comput. Surv., 42, 1, 2:1-2:32 (2009) · doi:10.1145/1592451.1592453
[24] Cygan, M., Kowalik, L., Socala, A.: Improving TSP tours using dynamic programming over tree decompositions. In: 25th Annual European Symposium on Algorithms, ESA 2017, pp. 30:1-30:14, (2017) · Zbl 1442.68286
[25] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 3, 353-366 (1989) · Zbl 0665.68084 · doi:10.1016/0004-3702(89)90037-4
[26] Downey, R.G., Fellows, M.R.: Parameterized Complexity Monographs in Computer Science. Springer, Berlin(999)
[27] Dujmovic, V.; Eppstein, D.; Wood, DR, Structure of graphs with locally restricted crossings, SIAM J. Discrete Math., 31, 2, 805-824 (2017) · Zbl 1362.05121 · doi:10.1137/16M1062879
[28] Erdős, P.; Szekeres, G., A combinatorial problem in geometry, Compos. Math., 2, 463-470 (1935) · Zbl 0012.27010
[29] Fomin, FV; Gaspers, S.; Saurabh, S.; Stepanov, AA, On two techniques of combining branching and treewidth, Algorithmica, 54, 2, 181-207 (2009) · Zbl 1185.68475 · doi:10.1007/s00453-007-9133-3
[30] Fomin, FV; Høie, K., Pathwidth of cubic graphs and exact algorithms, Inf. Process. Lett., 97, 5, 191-196 (2006) · Zbl 1191.68826 · doi:10.1016/j.ipl.2005.10.012
[31] Fox, J.: Stanley-wilf limits are typically exponential. CoRR, arxiv: abs/1310.8378, 2013
[32] Fox, J., Wei, F.: Fast property testing and metrics for permutations. Combinatorics, Probability and Computing, pp. 1-41 (2018)
[33] Freuder, E.C.: Complexity of k-tree structured constraint satisfaction problems. In: Proceedings of the Eighth National Conference on Artificial Intelligence - Volume 1, AAAI’90, pp 4-9. AAAI Press, (1990)
[34] Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 82-101 (2014) · Zbl 1421.68083
[35] Guillemot, S.; Vialette, S.; Dong, Y.; Du, D-Z; Ibarra, O., Pattern matching for 321-avoiding permutations, Algorithms and Computation, 1064-1073 (2009), Berlin Heidelberg: Springer, Berlin Heidelberg · Zbl 1273.68422 · doi:10.1007/978-3-642-10631-6_107
[36] Hoffmann, K.; Mehlhorn, K.; Rosenstiehl, P.; Tarjan, RE, Sorting jordan sequences in linear time using level-linked search trees, Inf. Control, 68, 1-3, 170-184 (1986) · Zbl 0614.68051 · doi:10.1016/S0019-9958(86)80033-X
[37] Ibarra, L., Finding pattern matchings for permutations, Inf. Process. Lett., 61, 6, 293-295 (1997) · Zbl 1337.68305 · doi:10.1016/S0020-0190(97)00029-X
[38] Jelínek, V., Kyncl, J.: Hardness of permutation pattern matching. Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 378-396 (2017) · Zbl 1410.68146
[39] Keogh, E.J., Lonardi, S., Yuan-chi Chiu, B.: Finding surprising patterns in a time series database in linear time and space. In: Proceedings of the Eighth ACM SIGKDD 2002 International Conference on Knowledge Discovery and Data Mining, pp. 550-556, (2002)
[40] Kitaev, S., Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series (2011), Berlin: Springer, Berlin · Zbl 1257.68007
[41] Knuth, DE, The Art of Computer Programming, Volume I: Fundamental Algorithms (1968), Boston: Addison-Wesley, Boston · Zbl 0191.17903
[42] Knuth, Donald E., Estimating the efficiency of backtrack programs, Math. Comput., 29, 129, 122-136 (1975) · Zbl 0297.68037 · doi:10.1090/S0025-5718-1975-0373371-6
[43] Knuth, D.E.: Dancing links. arXiv preprint cs/0011047, (2000)
[44] Marcus, A.; Tardos, G., Excluded permutation matrices and the stanley-wilf conjecture, J. Comb. Theory Ser. A, 107, 1, 153-160 (2004) · Zbl 1051.05004 · doi:10.1016/j.jcta.2004.04.002
[45] Marx, D., Can you beat treewidth?, Theory Comput., 6, 1, 85-112 (2010) · Zbl 1213.68316 · doi:10.4086/toc.2010.v006a005
[46] Neou, B., Rizzi, R., Vialette, S.: Permutation Pattern matching in (213, 231)-avoiding permutations. Discrete Mathematics & Theoretical Computer Science, Vol. 18 no. 2, Permutation Patterns 2015, March 2017 · Zbl 1400.05013
[47] Newman, I., Rabinovich, Y., Rajendraprasad, D., Sohler, C.: Testing for forbidden order patterns in an array. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, pp. 1582-1597 (2017) · Zbl 1403.68338
[48] Nijenhuis, A.; Wilf, HS, Combinatorial Algorithms (1978), New York-London: Academic Press Inc., Harcourt Brace Jovanovich, New York-London · Zbl 0476.68047
[49] Patel, P., Keogh, E., Lin, J., Lonardi, S.: Mining motifs in massive time series databases. In: In Proceedings of IEEE International Conference on Data Mining ICDM’02, pp. 370-377, (2002)
[50] Pratt, V.R.: Computing permutations with double-ended queues, parallel stacks and parallel queues. In: Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC ’73, pp 268-277. ACM, (1973) · Zbl 0314.94030
[51] Rosenstiehl, P.; Bollobás, B.; Erdős, P., Planar permutations defined by two intersecting Jordan curves, Graph Theory and Combinatorics, 259-271 (1984), London: Academic Press, London · Zbl 0551.05004
[52] Rosenstiehl, P.; Tarjan, RE, Gauss codes, planar hamiltonian graphs, and stack-sortable permutations, J. Algorithms, 5, 3, 375-390 (1984) · Zbl 0588.68034 · doi:10.1016/0196-6774(84)90018-X
[53] Seidel, R.: A new method for solving constraint satisfaction problems. In: Proceedings of the 7th International Joint Conference on Artificial Intelligence, IJCAI 1981, pp. 338-342, (1981)
[54] Simion, R.; Schmidt, FW, Restricted permutations, Eur. J. Comb., 6, 4, 383-406 (1985) · Zbl 0615.05002 · doi:10.1016/S0195-6698(85)80052-4
[55] Sloane, N.J.A.: The encyclopedia of integer sequences, http://oeis.org. Sequence A073028 · Zbl 1044.11108
[56] Tanny, SM; Zuker, M., On a unimodal sequence of binomial coefficients, Discrete Math., 9, 1, 79-89 (1974) · Zbl 0284.05005 · doi:10.1016/0012-365X(74)90073-9
[57] Tarjan, RE, Sorting using networks of queues and stacks, J. ACM, 19, 2, 341-346 (1972) · Zbl 0243.68004 · doi:10.1145/321694.321704
[58] Tsang, EPK, Foundations of Constraint Satisfaction. Computation in Cognitive Science (1993), Cambridge: Academic Press, Cambridge
[59] Vatter, V.: Permutation classes. In Miklós Bóna, editor, Handbook of Enumerative Combinatorics, chapter 12. Chapman and Hall/CRC, New York, 2015. Preprint at arxiv: abs/1409.5159 · Zbl 1353.05010
[60] Yugandhar, V., Saxena, Sanjeev: Parallel algorithms for separable permutations, Discrete Appl. Math., 146, 3, 343-364 (2005) · Zbl 1085.68183 · doi:10.1016/j.dam.2004.10.004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.