Document Open Access Logo

Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs

Authors Bartłomiej Dudek , Paweł Gawrychowski

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.23.pdf
  • Filesize: 0.62 MB
  • 18 pages

Document Identifiers

Author Details

Bartłomiej Dudek
  • Institute of Computer Science, University of Wrocław, Poland
Paweł Gawrychowski
  • Institute of Computer Science, University of Wrocław, Poland

Funding

  • Dudek, Bartłomiej: partially supported by the National Science Centre, Poland, grant number 2017/27/N/ST6/02719.

Cite AsGet BibTex

Bartłomiej Dudek and Paweł Gawrychowski. Counting 4-Patterns in Permutations Is Equivalent to Counting 4-Cycles in Graphs. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.23

Abstract

Permutation σ appears in permutation π if there exists a subsequence of π that is order-isomorphic to σ. The natural algorithmic question is to check if σ appears in π, and if so count the number of occurrences. Only since very recently we know that for any fixed length k, we can check if a given pattern of length k appears in a permutation of length n in time linear in n, but being able to count all such occurrences in f(k)⋅ n^o(k/log k) time would refute the exponential time hypothesis (ETH). Together with practical applications in statistics, this motivates a systematic study of the complexity of counting occurrences for different patterns of fixed small length k. We investigate this question for k = 4. Very recently, Even-Zohar and Leng [arXiv 2019] identified two types of 4-patterns. For the first type they designed an 𝒪̃(n) time algorithm, while for the second they were able to provide an 𝒪̃(n^1.5) time algorithm. This brings up the question whether the permutations of the second type are inherently harder than the first type. We establish a connection between counting 4-patterns of the second type and counting 4-cycles (not necessarily induced) in a sparse undirected graph. By designing two-way reductions we show that the complexities of both problems are the same, up to polylogarithmic factors. This allows us to leverage the work done on the latter to provide a reasonable argument for why there is a difference in the complexities for counting 4-patterns of the first and the second type. In particular, even for the seemingly simpler problem of detecting a 4-cycle in a graph on m edges, the best known algorithm works in 𝒪(m^{4/3}) time. Our reductions imply that an 𝒪(n^{4/3-ε}) time algorithm for counting occurrences of any 4-pattern of the second type in a permutation of length n would imply an exciting breakthrough for counting (and hence also detecting) 4-cycles. In the other direction, by plugging in the fastest known algorithm for counting 4-cycles, we obtain an algorithm for counting occurrences of any 4-pattern of the second type in 𝒪(n^1.48) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithm design techniques
Keywords
  • Permutations
  • pattern avoidance
  • counting cycles

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In 55th FOCS, pages 434-443. IEEE Computer Society, 2014. Google Scholar
  2. Shlomo Ahal and Yuri Rabinovich. On complexity of the subpattern problem. SIAM J. Discrete Math., 2:629-649, 2008. Google Scholar
  3. Michael H. Albert, Robert E. L. Aldred, Mike D. Atkinson, and Derek A. Holton. Algorithms for pattern involvement in permutations. In 12th ISAAC, Lecture Notes in Computer Science, pages 355-366. Springer, 2001. Google Scholar
  4. Michael H. Albert, Marie-Louise Lackner, Martin Lackner, and Vincent Vatter. The complexity of pattern matching for 321-avoiding and skew-merged permutations. Discrete Mathematics & Theoretical Computer Science, 18(2), 2016. Google Scholar
  5. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 3:209-223, 1997. Google Scholar
  6. Sergey V. Avgustinovich, Sergey Kitaev, and Alexandr Valyuzhenich. Avoidance of boxed mesh patterns on permutations. Discrete Applied Mathematics, 1-2:43-51, 2013. Google Scholar
  7. Eric Babson and Einar Steingrímsson. Generalized permutation patterns and a classification of the mahonian statistics. Séminaire Lotharingien de Combinatoire, pages B44b, 18 p., 2000. Google Scholar
  8. Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and counting permutations via CSPs. In 14th IPEC, LIPIcs, pages 1:1-1:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  9. Wicher Bergsma and Angelos Dassios. A consistent test of independence based on a sign covariance related to Kendall’s tau. Bernoulli, 2:1006-1028, 2014. Google Scholar
  10. Miklós Bóna. Combinatorics of Permutations, Second Edition. Discrete mathematics and its applications. CRC Press, 2012. Google Scholar
  11. John Adrian Bondy and Miklós Simonovits. Cycles of even length in graphs. Journal of Combinatorial Theory, Series B, 2:97-105, 1974. Google Scholar
  12. Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations. Inf. Process. Lett., 5:277-283, 1998. Google Scholar
  13. Mireille Bousquet-Mélou, Anders Claesson, Mark Dukes, and Sergey Kitaev. (2+2)-free posets, ascent sequences and pattern avoiding permutations. J. Comb. Theory, Ser. A, 7:884-909, 2010. Google Scholar
  14. Petter Brändén and Anders Claesson. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electr. J. Comb., 2, 2011. Google Scholar
  15. Marie-Louise Bruner and Martin Lackner. The computational landscape of permutation patterns. CoRR, abs/1301.0340, 2013. URL: http://arxiv.org/abs/1301.0340.
  16. Marie-Louise Bruner and Martin Lackner. A fast algorithm for permutation pattern matching based on alternating runs. Algorithmica, 75(1):84-117, 2016. Google Scholar
  17. Timothy M. Chan and Mihai Pǎtraşcu. Counting inversions, offline orthogonal range counting, and related problems. In 21st SODA, pages 161-173. SIAM, 2010. Google Scholar
  18. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427-462, 1988. Google Scholar
  19. Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel. Finding even cycles faster via capped k-walks. In 49th STOC, pages 112-120. ACM, 2017. Google Scholar
  20. Bartłomiej Dudek and Paweł Gawrychowski. Computing quartet distance is equivalent to counting 4-cycles. In 51st STOC, pages 733-743. ACM, 2019. Google Scholar
  21. Lech Duraj, Krzysztof Kleiner, Adam Polak, and Virginia Vassilevska Williams. Equivalences between triangle and range query problems. In 30th SODA, pages 30-47. SIAM, 2020. Google Scholar
  22. Sergi Elizalde and Marc Noy. Consecutive patterns in permutations. Adv. Appl. Math., 1-2:110-125, 2003. Google Scholar
  23. Paul Erdős and George Szekeres. A combinatorial problem in geometry. Compositio Mathematica, pages 463-470, 1935. Google Scholar
  24. Chaim Even-Zohar and Calvin Leng. Counting small permutation patterns. CoRR, abs/1911.01414, 2019. URL: http://arxiv.org/abs/1911.01414.
  25. Jacob Fox. Stanley-Wilf limits are typically exponential. CoRR, abs/1310.8378, 2013. URL: http://arxiv.org/abs/1310.8378.
  26. Francois Le Gall. Powers of tensors and fast matrix multiplication. In 25th ISSAC, pages 296-303. ACM, 2014. Google Scholar
  27. Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In 25th SODA, pages 82-101. SIAM, 2014. Google Scholar
  28. Sylvain Guillemot and Stéphane Vialette. Pattern matching for 321-avoiding permutations. In 20th ISAAC, volume 5878 of Lecture Notes in Computer Science, pages 1064-1073. Springer, 2009. Google Scholar
  29. Ruth Heller, Yair Heller, Shachar Kaufman, Barak Brill, and Malka Gorfine. Consistent distribution-free k-sample and independence tests for univariate random variables. J. Mach. Learn. Res., pages 29:1-29:54, 2016. Google Scholar
  30. Yair Heller and Ruth Heller. Computing the Bergsma Dassios sign-covariance. CoRR, abs/1605.08732, 2016. URL: http://arxiv.org/abs/1605.08732.
  31. Wassily Hoeffding. A non-parametric test of independence. The Annals of Mathematical Statistics, pages 546-557, 1948. Google Scholar
  32. Louis Ibarra. Finding pattern matchings for permutations. Inf. Process. Lett., 61(6):293-295, 1997. Google Scholar
  33. Joseph JáJá, Christian Worm Mortensen, and Qingmin Shi. Space-efficient and fast algorithms for multidimensional dominance reporting and counting. In 15th ISAAC, volume 3341 of Lecture Notes in Computer Science, pages 558-568. Springer, 2004. Google Scholar
  34. Vít Jelínek and Jan Kynčl. Hardness of permutation pattern matching. In 28th SODA, pages 378-396. SIAM, 2017. Google Scholar
  35. Maurice G. Kendall. A new measure of rank correlation. Biometrika, pages 81-93, 1938. Google Scholar
  36. Sergey Kitaev. Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2011. Google Scholar
  37. Donald E. Knuth. The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley, 1968. Google Scholar
  38. Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. Tight hardness for shortest cycles and paths in sparse graphs. In 29th SODA, pages 1236-1252. SIAM, 2018. Google Scholar
  39. Adam Marcus and Gábor Tardos. Excluded permutation matrices and the Stanley-Wilf conjecture. J. Comb. Theory, Ser. A, 1:153-160, 2004. Google Scholar
  40. Rodica Simion and Frank W. Schmidt. Restricted permutations. Eur. J. Comb., 4:383-406, 1985. Google Scholar
  41. Vincent Vatter. Permutation classes. In Miklós Bóna, editor, Handbook of Enumerative Combinatorics. CRC Press, 2015. Preprint at URL: https://arxiv.org/abs/1409.5159.
  42. Luca Weihs, Mathias Drton, and Dennis Leung. Efficient computation of the Bergsma - Dassios sign covariance. Comput. Stat., 1:315-328, 2016. Google Scholar
  43. Luca Weihs, Mathias Drton, and Nicolai Meinshausen. Symmetric rank covariances: a generalized framework for nonparametric measures of dependence. Biometrika, 3:547-562, 2018. Google Scholar
  44. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In 44th STOC, pages 887-898. ACM, 2012. Google Scholar
  45. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In International Congress of Mathematicians (ICM), 2018. Google Scholar
  46. Virginia Vassilevska Williams, Joshua R. Wang, Richard Ryan Williams, and Huacheng Yu. Finding four-node subgraphs in triangle time. In 26th SODA, pages 1671-1680. SIAM, 2015. Google Scholar
  47. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. J. ACM, 5:27:1-27:38, 2018. Google Scholar
  48. Takemi Yanagimoto. On measures of association and a related problem. Annals of the Institute of Statistical Mathematics, 1:57-63, 1970. Google Scholar
  49. V. Yugandhar and Sanjeev Saxena. Parallel algorithms for separable permutations. Discrete Applied Mathematics, 3:343-364, 2005. Google Scholar
  50. Raphael Yuster and Uri Zwick. Finding even cycles even faster. SIAM J. Discrete Math., 2:209-222, 1997. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact