Document Open Access Logo

Generalized Coloring of Permutations

Authors Vít Jelínek , Michal Opler , Pavel Valtr

PDF
Thumbnail PDF

File

LIPIcs.ESA.2018.50.pdf
  • Filesize: 495 kB
  • 14 pages

Document Identifiers

Author Details

Vít Jelínek
  • Computer Science Institute, Charles University, Malostranské náměstí 25, Praha 1, 11800, Czechia
Michal Opler
  • Computer Science Institute, Charles University, Malostranské náměstí 25, Praha 1, 11800, Czechia
Pavel Valtr
  • Department of Applied Mathematics, Charles University, Malostranské náměstí 25, Praha 1, 11800, Czechia

Funding

Supported by the GAUK project 1766318, by project Impuls of the Neuron Fund for Support of Science, and by project 18-19158S of the Czech Science Foundation.

Cite As Get BibTex

Vít Jelínek, Michal Opler, and Pavel Valtr. Generalized Coloring of Permutations. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ESA.2018.50

Abstract

A permutation pi is a merge of a permutation sigma and a permutation tau, if we can color the elements of pi red and blue so that the red elements have the same relative order as sigma and the blue ones as tau. We consider, for fixed hereditary permutation classes C and D, the complexity of determining whether a given permutation pi is a merge of an element of C with an element of D.
We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of nondeterministic logspace streaming recognizability of permutations, which we introduce, and a concept of bounded width decomposition, inspired by the work of Ahal and Rabinovich.
As a consequence of the general results, we can provide nontrivial examples of tractable permutation merges involving commonly studied permutation classes, such as the class of layered permutations, the class of separable permutations, or the class of permutations avoiding a decreasing sequence of a given length.
On the negative side, we obtain a general hardness result which implies, for example, that it is NP-complete to recognize the permutations that can be merged from two subpermutations avoiding the pattern 2413.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Permutations and combinations
  • Mathematics of computing → Combinatorial algorithms
  • Theory of computation → Problems, reductions and completeness
Keywords
  • Permutations
  • merge
  • generalized coloring

Metrics

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

References

  1. D. Achlioptas, J. I. Brown, D. G. Corneil, and M. S. O. Molloy. The existence of uniquely -G colourable graphs. Discrete Math., 179(1-3):1-11, 1998. URL: http://dx.doi.org/10.1016/S0012-365X(97)00022-8.
  2. S. Ahal and Y. Rabinovich. On complexity of the subpattern problem. SIAM J. Discrete Math., 22(2):629-649, 2008. URL: http://dx.doi.org/10.1137/S0895480104444776.
  3. M. Albert and V. Jelínek. Unsplittable classes of separable permutations. Electron. J. Combin., 23(2):Paper 2.49, 20, 2016. Google Scholar
  4. M. Albert, J. Pantone, and V. Vatter. On the growth of merges and staircases of permutation classes. arXiv:1608.06969, 2016. Google Scholar
  5. M. H. Albert. On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation. Random Structures Algorithms, 31(2):227-238, 2007. URL: http://dx.doi.org/10.1002/rsa.20140.
  6. V. E. Alekseev, A. Farrugia, and V. V. Lozin. New results on generalized graph coloring. Discrete Math. Theor. Comput. Sci., 6(2):215-221, 2004. Google Scholar
  7. D. Bevan, R. Brignall, A. Elvey Price, and J. Pantone. Staircases, dominoes, and the growth rate of 1324-avoiders. Electronic Notes in Discrete Mathematics, 61:123-129, 2017. The European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB'17). URL: http://dx.doi.org/10.1016/j.endm.2017.06.029.
  8. M. Bóna. A new upper bound for 1324-avoiding permutations. Combin. Probab. Comput., 23(5):717-724, 2014. URL: http://dx.doi.org/10.1017/S0963548314000091.
  9. M. Bóna. A new record for 1324-avoiding permutations. Eur. J. Math., 1(1):198-206, 2015. URL: http://dx.doi.org/10.1007/s40879-014-0020-6.
  10. P. Borowiecki. Computational aspects of greedy partitioning of graphs. J. Comb. Optim., 35(2):641-665, 2018. URL: http://dx.doi.org/10.1007/s10878-017-0185-2.
  11. P. Bose, J. F. Buss, and A. Lubiw. Pattern matching for permutations. Inform. Process. Lett., 65(5):277-283, 1998. URL: http://dx.doi.org/10.1016/S0020-0190(97)00209-3.
  12. J. I. Brown. The complexity of generalized graph colorings. Discrete Appl. Math., 69(3):257-270, 1996. URL: http://dx.doi.org/10.1016/0166-218X(96)00096-0.
  13. A. Claesson, V. Jelínek, and E. Steingrímsson. Upper bounds for the Stanley-Wilf limit of 1324 and other layered patterns. J. Comb. Theory A, 119:1680-1691, 2012. Google Scholar
  14. T. Ekim, P. Heggernes, and D. Meister. Polar permutation graphs are polynomial-time recognisable. European J. Combin., 34(3):576-592, 2013. URL: http://dx.doi.org/10.1016/j.ejc.2011.12.007.
  15. A. Farrugia. Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin., 11(1):Research Paper 46, 9, 2004. Google Scholar
  16. S. Guillemot and D. 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: http://dx.doi.org/10.1137/1.9781611973402.7.
  17. V. Jelínek and M. Opler. Splittability and 1-amalgamability of permutation classes. Discrete Math. Theor. Comput. Sci., 19(2):Paper No. 4, 14, 2017. Google Scholar
  18. V. Jelínek and P. Valtr. Splittings and Ramsey properties of permutation classes. Adv. Appl. Math., 63:41-67, 2015. URL: http://dx.doi.org/10.1016/j.aam.2014.10.003.
  19. A. E. Kézdy, H. S. Snevily, and C. Wang. Partitioning permutations into increasing and decreasing subsequences. J. Combin. Theory Ser. A, 73(2):353-359, 1996. Google Scholar
  20. V. Rutenburg. Complexity of generalized graph coloring. In Mathematical foundations of computer science, 1986 (Bratislava, 1986), volume 233 of Lecture Notes in Comput. Sci., pages 573-581. Springer, Berlin, 1986. URL: http://dx.doi.org/10.1007/BFb0016284.
  21. V. Vatter. An Erdős-Hajnal analogue for permutation classes. Discrete Math. Theor. Comput. Sci., 18(2):Paper No. 4, 5, 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