Document Open Access Logo

Permutation Pattern Matching for Doubly Partially Ordered Patterns

Authors Laurent Bulteau , Guillaume Fertin , Vincent Jugé, Stéphane Vialette

PDF
Thumbnail PDF

File

LIPIcs.CPM.2022.21.pdf
  • Filesize: 1.16 MB
  • 17 pages

Document Identifiers

Author Details

Laurent Bulteau
  • LIGM, CNRS, Univ Gustave Eiffel, F77454 Marne-la-Vallée, France
Guillaume Fertin
  • Nantes Université, LS2N (UMR 6004), CNRS, Nantes, France
Vincent Jugé
  • LIGM, CNRS, Univ Gustave Eiffel, F77454 Marne-la-Vallée, France
Stéphane Vialette
  • LIGM, CNRS, Univ Gustave Eiffel, F77454 Marne-la-Vallée, France

Cite As Get BibTex

Laurent Bulteau, Guillaume Fertin, Vincent Jugé, and Stéphane Vialette. Permutation Pattern Matching for Doubly Partially Ordered Patterns. In 33rd Annual Symposium on Combinatorial Pattern Matching (CPM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 223, pp. 21:1-21:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.CPM.2022.21

Abstract

We study in this paper the Doubly Partially Ordered Pattern Matching (or DPOP Matching) problem, a natural extension of the Permutation Pattern Matching problem. Permutation Pattern Matching takes as input two permutations σ and π, and asks whether there exists an occurrence of σ in π; whereas DPOP Matching takes two partial orders P_v and P_p defined on the same set X and a permutation π, and asks whether there exist |X| elements in π whose values (resp., positions) are in accordance with P_v (resp., P_p). Posets P_v and P_p aim at relaxing the conditions formerly imposed by the permutation σ, since σ yields a total order on both positions and values. Our problem being NP-hard in general (as Permutation Pattern Matching is), we consider restrictions on several parameters/properties of the input, e.g., bounding the size of the pattern, assuming symmetry of the posets (i.e., P_v and P_p are identical), assuming that one partial order is a total (resp., weak) order, bounding the length of the longest chain/anti-chain in the posets, or forbidding specific patterns in π. For each such restriction, we provide results which together give a(n almost) complete landscape for the algorithmic complexity of the problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Partial orders
  • Permutations
  • Pattern Matching
  • Algorithmic Complexity
  • Parameterized Complexity

Metrics

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

References

  1. Shlomo Ahal and Yuri Rabinovich. On complexity of the subpattern problem. SIAM J. Discret. Math., 22(2):629-649, 2008. Google Scholar
  2. Michael H. Albert, Marie-Louise Lackner, Martin Lackner, and Vincent Vatter. The complexity of pattern matching for 321-avoiding and skew-merged permutations. Discret. Math. Theor. Comput. Sci., 18(2), 2016. Google Scholar
  3. Sergey V. Avgustinovich, Sergey Kitaev, and Alexandr Valyuzhenich. Avoidance of boxed mesh patterns on permutations. Discret. Appl. Math., 161(1-2):43-51, 2013. Google Scholar
  4. Eric Babson and Einar Steingrímsson. Generalized permutation patterns and a classification of the mahonian statistics. Séminaire Lotharingien de Combinatoire [electronic only], 44:B44b, 18 p.-B44b, 18 p., 2000. URL: http://eudml.org/doc/120841.
  5. Benjamin Aram Berendsohn, László Kozma, and Dániel Marx. Finding and counting permutations via csps. Algorithmica, 83(8):2552-2577, 2021. Google Scholar
  6. Miklós Bóna. Combinatorics of Permutations, Second Edition. Discrete mathematics and its applications. CRC Press, 2012. Google Scholar
  7. Prosenjit Bose, Jonathan F. Buss, and Anna Lubiw. Pattern matching for permutations. Inf. Process. Lett., 65(5):277-283, 1998. Google Scholar
  8. 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, 117(7):884-909, 2010. Google Scholar
  9. Petter Brändén and Anders Claesson. Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electron. J. Comb., 18(2), 2011. Google Scholar
  10. 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
  11. Laurent Bulteau, Romeo Rizzi, and Stéphane Vialette. Pattern matching for k-track permutations. In Costas S. Iliopoulos, Hon Wai Leong, and Wing-Kin Sung, editors, Combinatorial Algorithms - 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings, volume 10979 of Lecture Notes in Computer Science, pages 102-114. Springer, 2018. Google Scholar
  12. Maxime Crochemore and Ely Porat. Fast computation of a longest increasing subsequence and application. Inf. Comput., 208(9):1054-1059, 2010. Google Scholar
  13. Sergi Elizalde and Marc Noy. Consecutive patterns in permutations. Adv. Appl. Math., 30(1-2):110-125, 2003. Google Scholar
  14. Paul Erdös and George Szekeres. A combinatorial problem in geometry. Compositio mathematica, 2:463-470, 1935. Google Scholar
  15. Jacob Fox. Stanley-wilf limits are typically exponential. CoRR, abs/1310.8378, 2013. URL: http://arxiv.org/abs/1310.8378.
  16. Paweł Gawrychowski and Mateusz Rzepecki. Faster exponential algorithm for permutation pattern matching. In Symposium on Simplicity in Algorithms (SOSA), pages 279-284. SIAM, 2022. Google Scholar
  17. Sylvain Guillemot and Dániel Marx. Finding small patterns in permutations in linear time. In Chandra Chekuri, editor, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014, pages 82-101. SIAM, 2014. Google Scholar
  18. Sylvain Guillemot and Stéphane Vialette. Pattern matching for 321-avoiding permutations. In Yingfei Dong, Ding-Zhu Du, and Oscar H. Ibarra, editors, Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, volume 5878 of Lecture Notes in Computer Science, pages 1064-1073. Springer, 2009. Google Scholar
  19. Louis Ibarra. Finding pattern matchings for permutations. Inf. Process. Lett., 61(6):293-295, 1997. Google Scholar
  20. Klaus Jansen, Stefan Kratsch, Dániel Marx, and Ildikó Schlotter. Bin packing with fixed number of bins revisited. J. Comput. Syst. Sci., 79(1):39-49, 2013. Google Scholar
  21. Vít Jelínek and Jan Kynčl. Hardness of permutation pattern matching. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 378-396. SIAM, 2017. Google Scholar
  22. Richard M. Karp. Reducibility among Combinatorial Problems, pages 85-103. Springer US, Boston, MA, 1972. Google Scholar
  23. Sergey Kitaev. Introduction to partially ordered patterns. Discret. Appl. Math., 155(8):929-944, 2007. Google Scholar
  24. Sergey Kitaev. Patterns in Permutations and Words. Monographs in Theoretical Computer Science. An EATCS Series. Springer, 2011. Google Scholar
  25. Both Emerite Neou, Romeo Rizzi, and Stéphane Vialette. Pattern matching for separable permutations. In Shunsuke Inenaga, Kunihiko Sadakane, and Tetsuya Sakai, editors, String Processing and Information Retrieval - 23rd International Symposium, SPIRE 2016, Beppu, Japan, October 18-20, 2016, Proceedings, volume 9954 of Lecture Notes in Computer Science, pages 260-272, 2016. Google Scholar
  26. Both Emerite Neou, Romeo Rizzi, and Stéphane Vialette. Permutation pattern matching in (213, 231)-avoiding permutations. Discret. Math. Theor. Comput. Sci., 18(2), 2016. 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 About DROPS Imprint Privacy Contact