Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder

Authors Vít Jelínek , Michal Opler , Jakub Pekárek



PDF
Thumbnail PDF

File

LIPIcs.IPEC.2021.22.pdf
  • Filesize: 0.84 MB
  • 17 pages

Document Identifiers

Author Details

Vít Jelínek
  • Computer Science Institute, Charles University, Prague, Czech Republic
Michal Opler
  • Computer Science Institute, Charles University, Prague, Czech Republic
Jakub Pekárek
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic

Cite AsGet BibTex

Vít Jelínek, Michal Opler, and Jakub Pekárek. Long Paths Make Pattern-Counting Hard, and Deep Trees Make It Harder. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.IPEC.2021.22

Abstract

We study the counting problem known as #PPM, whose input is a pair of permutations π and τ (called pattern and text, respectively), and the task is to find the number of subsequences of τ that have the same relative order as π. A simple brute-force approach solves #PPM for a pattern of length k and a text of length n in time O(n^{k+1}), while Berendsohn, Kozma and Marx have recently shown that under the exponential time hypothesis (ETH), it cannot be solved in time f(k) n^{o(k/log k)} for any function f. In this paper, we consider the restriction of #PPM, known as 𝒞-Pattern #PPM, where the pattern π must belong to a hereditary permutation class 𝒞. Our goal is to identify the structural properties of 𝒞 that determine the complexity of 𝒞-Pattern #PPM. We focus on two such structural properties, known as the long path property (LPP) and the deep tree property (DTP). Assuming ETH, we obtain these results: 1) If 𝒞 has the LPP, then 𝒞-Pattern #PPM cannot be solved in time f(k)n^{o(√k)} for any function f, and 2) if 𝒞 has the DTP, then 𝒞-Pattern #PPM cannot be solved in time f(k)n^{o(k/log² k)} for any function f. Furthermore, when 𝒞 is one of the so-called monotone grid classes, we show that if 𝒞 has the LPP but not the DTP, then 𝒞-Pattern #PPM can be solved in time f(k)n^{O(√ k)}. In particular, the lower bounds above are tight up to the polylog terms in the exponents.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
  • Theory of computation → Pattern matching
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Permutation pattern matching
  • subexponential algorithm
  • conditional lower bounds
  • tree-width

Metrics

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

References

  1. Shlomo Ahal and Yuri Rabinovich. On complexity of the subpattern problem. SIAM J. Discrete Math., 22(2):629-649, 2008. URL: https://doi.org/10.1137/S0895480104444776.
  2. Benjamin Aram Berendsohn. Complexity of permutation pattern matching. Master’s thesis, Freie Universität Berlin, Berlin, 2019. Google Scholar
  3. Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and counting permutations via CSPs. In Bart M. P. Jansen and Jan Arne Telle, editors, 14th International Symposium on Parameterized and Exact Computation, IPEC 2019, September 11-13, 2019, Munich, Germany, volume 148 of LIPIcs, pages 1:1-1:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.IPEC.2019.1.
  4. Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations. Inform. Process. Lett., 65(5):277-283, 1998. URL: https://doi.org/10.1016/S0020-0190(97)00209-3.
  5. Karl Bringmann, László Kozma, Shay Moran, and N. S. Narayanaswamy. Hitting set for hypergraphs of low VC-dimension. In 24th Annual European Symposium on Algorithms, volume 57 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 23, 18. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016. Google Scholar
  6. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, Cham, 2015. URL: https://doi.org/10.1007/978-3-319-21275-3.
  7. Vida Dujmović, David Eppstein, and David R. Wood. Structure of graphs with locally restricted crossings. SIAM Journal on Discrete Mathematics, 31(2):805-824, 2017. URL: https://doi.org/10.1137/16M1062879.
  8. Jacob Fox. Stanley-Wilf limits are typically exponential. https://arxiv.org/abs/1310.8378v1, 2013.
  9. Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 82-101. ACM, New York, 2014. URL: https://doi.org/10.1137/1.9781611973402.7.
  10. Sylvain Guillemot and Stéphane Vialette. Pattern matching for 321-avoiding permutations. In Algorithms and computation, volume 5878 of Lecture Notes in Comput. Sci., pages 1064-1073. Springer, Berlin, 2009. URL: https://doi.org/10.1007/978-3-642-10631-6_107.
  11. Vít Jelínek and Jan Kynčl. Hardness of permutation pattern matching. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 378-396. SIAM, Philadelphia, PA, 2017. URL: https://doi.org/10.1137/1.9781611974782.24.
  12. Vít Jelínek, Michal Opler, and Jakub Pekárek. A complexity dichotomy for permutation pattern matching on grid classes. In Javier Esparza and Daniel Král', editors, 45th International Symposium on Mathematical Foundations of Computer Science, MFCS 2020, August 24-28, 2020, Prague, Czech Republic, volume 170 of LIPIcs, pages 52:1-52:18. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.MFCS.2020.52.
  13. Vít Jelínek, Michal Opler, and Jakub Pekárek. Griddings of Permutations and Hardness of Pattern Matching. In Filippo Bonchi and Simon J. Puglisi, editors, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), volume 202 of LIPIcs, pages 65:1-65:22. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.MFCS.2021.65.
  14. Dániel Marx. Can you beat treewidth? Theory Comput., 6:85-112, 2010. URL: https://doi.org/10.4086/toc.2010.v006a005.
  15. Vincent Vatter and Steve Waton. On partial well-order for monotone grid classes of permutations. Order, 28(2):193-199, 2011. URL: https://doi.org/10.1007/s11083-010-9165-1.
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