Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Generalized Coloring of Permutations

  • Published:
Algorithmica Aims and scope Submit manuscript

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 \(\mathcal {C}\) and \(\mathcal {D}\), the complexity of determining whether a given permutation \(\pi \) is a merge of an element of \(\mathcal {C}\) with an element of \(\mathcal {D}\). We develop general algorithmic approaches for identifying polynomially tractable cases of merge recognition. Our tools include a version of streaming recognizability of permutations via polynomially constructible nondeterministic automata, as well as 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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Data Availibility

There are no datasets associated with this work.

References

  1. Knuth, D.E.: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley Series in Computer Science and Information Processing, pp. 722–1. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. (1973)

  2. Brandstädt, A., Kratsch, D.: On partitions of permutations into increasing and decreasing subsequences. Elektron Informationsverarb Kybernet 22(5–6), 263–273 (1986)

    MathSciNet  Google Scholar 

  3. Stankova, Z.E.: Forbidden subsequences. Discrete Math. 132(1–3), 291–316 (1994). https://doi.org/10.1016/0012-365X(94)90242-9

    Article  MathSciNet  Google Scholar 

  4. Kézdy, A.E., Snevily, H.S., Wang, C.: Partitioning permutations into increasing and decreasing subsequences. J. Comb. Theory Ser. A 73(2), 353–359 (1996). https://doi.org/10.1016/S0097-3165(96)80012-4

    Article  MathSciNet  Google Scholar 

  5. Atkinson, M.D.: Permutations which are the union of an increasing and a decreasing subsequence. Electron. J. Comb. 5, 6–13 (1998) https://doi.org/10.37236/1344

  6. Murphy, M.M.: Restricted Permutations, Antichains, Atomic Classes and Stack SD thesis, University of St Andrews (2003)

  7. Albert, M.H.: On the length of the longest subsequence avoiding an arbitrary pattern in a random permutation. Random Struct. Algorithms 31(2), 227–238 (2007). https://doi.org/10.1002/rsa.20140

    Article  MathSciNet  Google Scholar 

  8. Albert, M., Pantone, J., Vatter, V.: On the growth of merges and staircases of permutation classes. Rocky Mt. J. Math. 49(2), 355–367 (2019). https://doi.org/10.1216/RMJ-2019-49-2-355

    Article  MathSciNet  Google Scholar 

  9. Claesson, A., Jelínek, V., Steingrímsson, E.: Upper bounds for the Stanley–Wilf limit of 1324 and other layered patterns. J. Comb. Theory Ser. A 119(8), 1680–1691 (2012). https://doi.org/10.1016/j.jcta.2012.05.006

    Article  MathSciNet  Google Scholar 

  10. Bóna, M.: A new upper bound for 1324-avoiding permutations. Comb. Probab. Comput. 23(5), 717–724 (2014). https://doi.org/10.1017/S0963548314000091

    Article  MathSciNet  Google Scholar 

  11. Bóna, M.: A new record for 1324-avoiding permutations. Eur. J. Math. 1(1), 198–206 (2015). https://doi.org/10.1007/s40879-014-0020-6

    Article  MathSciNet  Google Scholar 

  12. Bevan, D., Brignall, R., Elvey Price, A., Pantone, J.: A structural characterisation of \({\rm Av}(1324)\) and new bounds on its growth rate. Eur. J. Combin. 88, 103–115 (2020). https://doi.org/10.1016/j.ejc.2020.103115

    Article  MathSciNet  Google Scholar 

  13. Jelínek, V., Valtr, P.: Splittings and Ramsey properties of permutation classes. Adv. Appl. Math. 63, 41–67 (2015). https://doi.org/10.1016/j.aam.2014.10.003

    Article  MathSciNet  Google Scholar 

  14. Jelínek, V., Opler, M.: Splittability and 1-amalgamability of permutation classes. Discrete Math. Theor. Comput. Sci. 19(2), 4–14 (2017). https://doi.org/10.1109/mcse.2017.25

    Article  MathSciNet  Google Scholar 

  15. Albert, M., Jelínek, V.: Unsplittable classes of separable permutations. Electron. J. Comb. 23(2), 2–4920 (2016) https://doi.org/10.37236/6115

  16. Vatter, V.: An Erdős–Hajnal analogue for permutation classes. Discrete Math. Theor. Comput. Sci. 18(2), 4–5 (2016) https://doi.org/10.46298/dmtcs.1328

  17. Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277–283 (1998). https://doi.org/10.1016/S0020-0190(97)00209-3

    Article  MathSciNet  Google Scholar 

  18. Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM J. Discrete Math. 22(2), 629–649 (2008). https://doi.org/10.1137/S0895480104444776

    Article  MathSciNet  Google Scholar 

  19. 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, pp. 82–101. ACM, New York (2014). https://doi.org/10.1137/1.9781611973402.7

  20. Rutenburg, V.: Complexity of generalized graph coloring. In: Mathematical Foundations of Computer Science, 1986 (Bratislava, 1986). Lecture Notes in Computer Science, vol. 233, pp. 573–581. Springer, Berlin (1986). https://doi.org/10.1007/BFb0016284

  21. Farrugia, A.: Vertex-partitioning into fixed additive induced-hereditary properties is NP-hard. Electron. J. Combin. 11(1), 46–9 (2004) https://doi.org/10.37236/1799

  22. Brown, J.I.: The complexity of generalized graph colorings. Discrete Appl. Math. 69(3), 257–270 (1996). https://doi.org/10.1016/0166-218X(96)00096-0

    Article  MathSciNet  Google Scholar 

  23. Alekseev, V.E., Farrugia, A., Lozin, V.V.: New results on generalized graph coloring. Discrete Math. Theor. Comput. Sci. 6(2), 215–221 (2004) https://doi.org/10.46298/dmtcs.311

  24. Achlioptas, D., Brown, J.I., Corneil, D.G., Molloy, M.S.O.: The existence of uniquely \(-G\) colourable graphs. Discrete Math. 179(1–3), 1–11 (1998). https://doi.org/10.1016/S0012-365X(97)00022-8

    Article  MathSciNet  Google Scholar 

  25. Borowiecki, P.: Computational aspects of greedy partitioning of graphs. J. Comb. Optim. 35(2), 641–665 (2018). https://doi.org/10.1007/s10878-017-0185-2

    Article  MathSciNet  Google Scholar 

  26. Ekim, T., Heggernes, P., Meister, D.: Polar permutation graphs are polynomial-time recognisable. Eur. J. Comb. 34(3), 576–592 (2013). https://doi.org/10.1016/j.ejc.2011.12.007

    Article  MathSciNet  Google Scholar 

  27. Vatter, V.: Permutation classes. In: Handbook of Enumerative Combinatorics. Discrete Mathematics Applications (Boca Raton), pp. 753–833. CRC Press, Boca Raton, FL (2015)

  28. Vatter, V.: Growth rates of permutation classes: from countable to uncountable. Proc. Lond. Math. Soc. 119(4), 960–997 (2019). https://doi.org/10.1112/plms.12250

    Article  MathSciNet  Google Scholar 

  29. Berendsohn, B.A.: Complexity of Permutation Pattern Matching. Master’s thesis, Freie Universität Berlin (2019)

  30. Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press, Cambridge (1997)

    Google Scholar 

  31. Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications (2007). Available on: http://tata.gforge.inria.fr/

  32. Jelínek, V., Opler, M., Pekárek, J.: Long paths make pattern-counting hard, and deep trees make it harder. In: 16th International Symposium on Parameterized and Exact Computation. LIPIcs Leibniz International Proceedings of the Informatics, vol. 214, pp. 22–17. Schloss Dagstuhl Leibniz-Zent Informatics, Wadern (2021). https://doi.org/10.4230/LIPIcs.IPEC.2021.22

  33. Jelínek, V., Kynčl, J.: Hardness of permutation pattern matching. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 378–396. SIAM, Philadelphia, PA (2017). https://doi.org/10.1137/1.9781611974782.24

  34. Jelínek, V., Opler, M., Pekárek, J.: A complexity dichotomy for permutation pattern matching on grid classes. In: 45th International Symposium on Mathematical Foundations of Computer Science. LIPIcs Leibniz International Proceedings of the Informatics, vol. 170, pp. 52–18. Schloss Dagstuhl Leibniz-Zent Informatics, Wadern (2020). https://doi.org/10.4230/LIPIcs.MFCS.2020.52

  35. Albert, M., Brignall, R., Ruškuc, N., Vatter, V.: Rationality for subclasses of 321-avoiding permutations. Eur. J. Comb. 78, 44–72 (2019). https://doi.org/10.1016/j.ejc.2019.01.001

    Article  MathSciNet  Google Scholar 

  36. Bodlaender, H.L., Drange, P.G., Dregi, M.S., Fomin, F.V., Lokshtanov, D., Pilipczuk, M.: A \(c^kn\) 5-approximation algorithm for treewidth. SIAM J. Comput. 45(2), 317–378 (2016). https://doi.org/10.1137/130947374

    Article  MathSciNet  Google Scholar 

  37. Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inf. Comput. 85(1), 12–75 (1990). https://doi.org/10.1016/0890-5401(90)90043-H

    Article  MathSciNet  Google Scholar 

  38. Erdős, P., Szekeres, G.: A combinatorial problem in geometry. Compos. Math. 2, 463–470 (1935)

    MathSciNet  Google Scholar 

  39. Schaefer, T.J.: The complexity of satisfiability problems. In: Conference Record of the Tenth Annual ACM Symposium on Theory of Computing (San Diego, California, 1978), pp. 216–226. ACM, New York (1978)

  40. Hoàng, C.T., Le, V.B.: \(P_4\)-free colorings and \(P_4\)-bipartite graphs. Discrete Math. Theor. Comput. Sci. 4(2), 109–122 (2001) https://doi.org/10.46298/dmtcs.272

  41. Jelínek, V., Opler, M., Valtr, P.: Generalized coloring of permutations. In: 26th European Symposium on Algorithms. LIPIcs. Leibniz International Proceedings of the Informatics, vol. 112, pp. 50–14. Schloss Dagstuhl Leibniz-Zent Informatics, Wadern (2018). https://doi.org/10.4230/LIPIcs.ESA.2018.50

Download references

Funding

This research was supported by project GA21-32817 S of the Czech Science Foundation. An extended abstract of this paper has appeared in the proceedings of ESA 2018 [41]. The extended abstract omitted all the proofs of the main results, as well as all the material related to BD-recognizability. It also omitted the notion of PNA-recognizability and used a formally different notion of NLOL-recognizability instead.

Author information

Authors and Affiliations

  1. Computer Science Institute, Charles University, Prague, Czechia

    Vít Jelínek

  2. Faculty of Information Technology, Czech Technical University, Prague, Czechia

    Michal Opler

  3. Department of Applied Mathematics, Charles University, Prague, Czechia

    Pavel Valtr

Authors
  1. Vít Jelínek
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michal Opler
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Pavel Valtr
    View author publications

    You can also search for this author in PubMed Google Scholar

Contributions

The three coauthors contributed equally to this work.

Corresponding author

Correspondence to Vít Jelínek.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Jelínek, V., Opler, M. & Valtr, P. Generalized Coloring of Permutations. Algorithmica 86, 2174–2210 (2024). https://doi.org/10.1007/s00453-024-01220-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-024-01220-9

Keywords

Mathematics Subject Classification

Search

Navigation