vestifmИзвестия Национальной академии наук Беларуси. Серия физико-математических наукProceedings of the National Academy of Sciences of Belarus. Physics and Mathematics Series1561-24302524-2415The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"10.29235/1561-2430-2023-59-2-121-129vestifm-711Research ArticleМАТЕМАТИКАMATHEMATICSЗадача о ({K1, K2},k,l)-упаковке наибольшего веса в графеThe maximum weight ({K1,K2},k,l)-packing problem in a graphЛепинВ. В.LepinV. V.

Лепин Виктор Васильевич – кандидат физико-математических наук, ученый секретарь

ул. Сурганова, 11, 220072, Минск

Victor V. Lepin – Ph. D. (Physics and Mathematics), Scientific Secretary

Surganov Str., 11, 220072, Minsk

lepin@im.bas-net.byИнститут математики Национальной академии наук БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus202306072023592121129Copyright © Лепин В.В., 20232023Лепин В.В.Lepin V.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://vestifm.belnauka.by/jour/article/view/711

Рассматривается задача о ({K1,K2},k,l)-упаковке наибольшего веса в графе, которая обобщает ряд известных задач, например, о независимом множестве, максимальном индуцированном паросочетании, k-разделенном паросочетании, связном паросочетании, диссоциирующем множестве, k-упаковке. Показано, что в классе кографов ({K1,K2},k,l)-упаковку наибольшего веса можно найти за время O(n + m). Пусть Г – класс графов и Г* – класс всех простых (относительно модульной декомпозиции) порожденных подграфов из Г. Доказано, что если задача об оптимальной ({K1,K2},k,l)-упаковке графа может быть решена в классе графов Г* за время O(np ), где p ≥ 2 – константа, то эта задача может быть решена в классе графов Г за время O(np ). 

In this paper, we consider the maximum weight ({K1,K2},k,l)-packing problem in a graph. This problem generalizes a number of well-known problems, for example: maximum induced matching, k-separated matching, connected matching, independent set, dissociating set, k-packing. We show that in the class of cographs, a maximum weight ({K1,K2},k,l)- packing can be computed in O(n + m) time. Let Γ be a class of graphs and Γ* be a class of all simple (with respect to the modular decomposition) induced subgraphs from Γ. It is proven that if the maximum weight ({K1,K2},k,l)-packing problem can be solved in the class of graphs Г* in time O(np ), where p ≥ 2 is a constant, then this problem can be solved in the class of graphs Г in time O(np ). 

графупаковкамодульная декомпозицияиндуцированное паросочетаниеk-разделенное паросочетаниеk-упаковкаgraphpackingmodular decompositioninduced matchingk-independent setk-packingReferencesYuster R. Combinatorial and computational aspects of graph packing and graph decomposition / R. Yuster // Comput. Sci. Rev. – 2007. – Vol. 1, № 1. – P. 12–26. https://doi.org/10.1016/j.cosrev.2007.07.002Yuster R. Combinatorial and computational aspects of graph packing and graph decomposition. Computer Science Review, 2007, vol. 1, no. 1, pp. 12–26. https://doi.org/10.1016/j.cosrev.2007.07.002Joos, F. Equality of distance packing numbers / F. Joos, D. Rautenbach // Discrete Math. – 2015. – Vol. 338, № 12. – P. 2374–2377. https://doi.org/10.1016/j.disc.2015.06.003Joos F., Rautenbach D. Equality of Distance Packing Numbers. Discrete Mathematics, 2015, vol. 338, no. 12, pp. 2374–2377. https://doi.org/10.1016/j.disc.2015.06.003Brandstädt, A. On distance-3 matchings and induced matchings. / A. Brandstädt, R. Mosca // Discrete Appl. Math. – 2011. – Vol. 159, № 7, pp. 509–520. https://doi.org/10.1016/j.dam.2010.05.022Brandstädt A., Mosca R. On distance-3 matchings and induced matchings. Discrete Applied Mathematics, 2011, vol. 159, no. 7, pp. 509–520. https://doi.org/10.1016/j.dam.2010.05.022Computational complexity of maximum distance-(k,l) matchings in graphs / N. Brauner [et al.] // Международный конгресс по информатике: информационные системы и технологии: материалы Междунар. науч. конгресса, Минск, 31 окт. – 3 нояб. 2011 г.: в 2 ч. – Минск, 2011. – Ч. 1. – С. 341–346.Brauner N., Finke G., Jost V., Kovalyov M. V., Orlovich Yu. L., Pronin P. V., Waserhole A. Computational complexity of maximum distance-(k,l) matchings in graphs. Mezhdunarodnyi kongress po informatike: informatsionnye sistemy i tekhnologii: materialy mezhdunarodnogo nauchnogo kongressa, Minsk, 31 oktyabrya – 3 noyabrya 2011 g. [International Congress on Informatics: Information Systems and Technologies: Proceedings of the International Scientific Congress, Minsk, October 31 – November 3, 2011]. Minsk, 2011, part 2, pp. 341–346.Kartynnik Yu., Ryzhikov A. On Minimum Maximal Distance-k Matchings / Y. Kartynnik, A. Ryzhikov // Electron. Notes Discrete Math. – 2016. – Vol. 56. – P. 71–76. https://doi.org/10.1016/j.endm.2016.11.011Kartynnik Yu., Ryzhikov A. On Minimum Maximal Distance-k Matchings. Electronic Notes in Discrete Mathematics, 2016, vol. 56, pp. 71–76. https://doi.org/10.1016/j.endm.2016.11.011Topp, J. On packing and covering numbers of graphs / J. Topp, L. Volkmann // Discrete Math. – 1991. – Vol. 96, № 3. – P. 229–238. https://doi.org/10.1016/0012-365x(91)90316-tTopp J., Volkmann L. On packing and covering numbers of graphs. Discrete Mathematics, 1991, vol. 96, no. 3, pp. 229–238. https://doi.org/10.1016/0012-365x(91)90316-tMeir, A. Relations between packing and covering numbers of a tree / A. Meir, J. W. Moon // Pacific J. Math. – 1975. – Vol. 61, № 1. – P. 225–233. https://doi.org/10.2140/pjm.1975.61.225Meir A., Moon J. W. Relations between packing and covering numbers of a tree. Pacific Journal of Mathematics, 1975, vol. 61, no. 1, pp. 225–233. https://doi.org/10.2140/pjm.1975.61.225The complexity of dissociation set problems in graphs / Yu. Orlovich [et al.] // Discrete Appl. Math. – 2011. – Vol. 159, № 13. – P. 1352–1366. https://doi.org/10.1016/j.dam.2011.04.023Orlovich Yu., Dolgui A., Finke G., Gordon V., Werner F. The complexity of dissociation set problems in graphs. Discrete Applied Mathematics, 2011, vol. 159, no. 13, pp. 1352–1366. https://doi.org/10.1016/j.dam.2011.04.023Gallai, T. Transitiv orienterbare graphe / T. Gallai // Acta Math. Acad. Sci. Hungar. – 1967. – Vol. 18, № 1–2. – P. 25–66. https://doi.org/10.1007/bf02020961Gallai T. Transitiv orienterbare graphe. Acta Mathematica Academiae Scientiarum Hungaricae. 1967, vol. 18, no. 1–2, pp. 25–66. https://doi.org/10.1007/bf02020961James, L. O. Graph decomposition for undirected graphs / L. O. James, R. G. Stanton, D. D. Cowan // Proc. of the Third Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, Feb. 28 – March 2, 1972. – Florida, 1972. – P. 281–290.James L. O., Stanton R. G., Cowan D. D. Graph decomposition for undirected graphs. Proceedings of the Third Southeastern Conference on Combinatorics, Graph Theory, and Computing, Florida Atlantic University, Boca Raton, Februaru 28 – March 2, 1972. Florida, 1972, pp. 281–290.Simpler linear-time modular decomposition via recursive factorizing permutations / M. Tedder [et al.] // Int. Colloquium on Automata, Languages and Programming (ICALP 2008). – Berlin; Heidelberg: Springer, 2008. – P. 634–645. – (Lecture Notes in Computer Science, vol 5125). https://doi.org/10.1007/978-3-540-70575-8_52Tedder M., Corneil D., Habib M., Paul C. Simpler linear-time modular decomposition via recursive factorizing permutations. Int. Colloquium on Automata, Languages and Programming (ICALP 2008). Lecture Notes in Computer Science, vol 5125. Berlin; Heidelberg, Springer, 2008, pp. 634–645. https://doi.org/10.1007/978-3-540-70575-8_52

The authors declare that there are no conflicts of interest present.