УДК 519.1
MSC: 05C70
DOI: 10.21538/0134-4889-2022-28-2-114-142
Полный текст статьи (Full text)
Работа выполнена Д.С. Малышевым при поддержке РФФИ (проект № 20-51-04001), О.И. Дугиновым и Н.А. Шур — при поддержке БРФФИ (проект № Ф21РМ-001).
Подмножество вершин графа называется диссоциирующим, если степени вершин подграфа, порожденного этим подмножеством, не превосходят 1. Диссоциирующее множество максимально, если оно не содержится ни в каком другом диссоциирующем множестве с бо́льшим числом вершин. В данной работе предлагаются оценки наибольшего (наименьшего) числа вершин в максимальном диссоциирующем множестве графа. Доказано, что задача нахождения максимального диссоциирующего множества наибольшей мощности NP-трудна для квазихордальных двудольных графов. Кроме этого доказано, что задача нахождения максимального диссоциирующего множества наименьшей мощности NP-трудна для хордальных двудольных графов, двудольных графов с максимальной степенью вершин, равной 3, планарных графов с большим обхватом, а также для классов графов, характеризуемых конечными списками запрещенных порожденных двусвязных подграфов. Предлагается линейный алгоритм решения последней задачи в классе деревьев.
Ключевые слова: максимальное диссоциирующее множество графа, задача поиска наибольшего порожденного подграфа с максимальной степенью вершин не больше 1, максимальное диссоциирующее множество, квазихордальные двудольные графы, NP-полнота, наследственные классы графов, деревья
СПИСОК ЛИТЕРАТУРЫ
1. Лекции по теории графов: учебное пособие / В.А. Емеличев [и др.]. М.: КД “Либроком”, 2009. 392 с.
2. McLaughlan B., Akkaya K. Coverage-based Clustering of Wireless Sensor and Actor Networks // IEEE Internat. Conf. on Pervasive Services. 2007. P. 45–54. doi: 10.1109/PERSER.2007.4283888
3. Yannakakis M. Node-Deletion Problems on Bipartite Graphs // SIAM J. Comp. 1981. Vol. 10, no. 2. P. 310–327. doi: 10.1137/0210022 .
4. Boliac R., Cameron K., Lozin V. On computing the dissociation number and the induced matching number of bipartite graphs // Ars Combinatoria. 2004. Vol. 72. P. 241–253.
5. Boliac R., Lozin V. On computing the dissociation number of bipartite graphs // Rutcor research report. 2001. Art. no. 31-2001. 10 p.
6. The complexity of dissociation set problems in graphs / Yu. Orlovich et. al // Discrete Appl. Math. 2011. Vol. 159, no. 13. P. 1352–1366. doi: 10.1016/j.dam.2011.04.023
7. Cameron K., Hell P. Independent packings in structured graphs // Math. Programming, series B. 2006. Vol. 105, no. 2. P. 201–213. doi: 10.1007/s10107-005-0649-5
8. Lozin V., Rautenbach D. Some results on graphs without long induced paths // Inf. Process. Lett. 2003. Vol. 88. P. 167–171. doi: 10.1016/j.ipl.2003.07.004
9. Kardoš F., Katrenič J., Schiermeyer I. On computing the minimum 3-path vertex cover and dissociation number of graphs // Theoretical Comp. Sci. 2011. Vol. 412, no. 50. P. 7009–7017. doi: 10.1016/j.tcs.2011.09.009
10. Xiao M., Kou S. Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems // Theoretical Comp. Sci. 2017. Vol. 657, Part A. P. 86–97. doi: 10.1016/j.tcs.2016.04.043
11. Moderately exponential time algorithms for the maximum bounded-degree-1 set problem / M.-S. Chang et al. // Discret. Appl. Math. 2018. Vol. 251. P. 114–125. doi: 10.1016/j.dam.2018.05.032
12. On bounded-degree vertex deletion parameterized by treewidth / N. Betzler et al. // Discret. Appl. Math. 2012. Vol. 160, no. 1-2. P. 53–60. doi: 10.1016/j.dam.2011.08.013
13. Ganian R., Klute F., Ordyniak S. On structural parameterizations of the bounded-degree vertex deletion problem // Algorithmica. 2021. Vol. 83, no. 1. P. 297–336. doi: 10.1007/s00453-020-00758-8
14. Сложность задач о диссоциирующих множествах в некоторых наследственных классах графов / Ю. Л. Орлович и др. // Докл. Национал. Наук Беларуси. 2009. Т. 53. № 3. С. 16–20.
15. Tu J., Zhang Z., Shi Y. The maximum number of maximum dissociation sets in trees // J. Graph Theory. 2020. Vol. 96, no. 4. P. 472–489. doi: 10.1002/jgt.22627
16. Brešar B., Hartnell B., Rall D. Uniformly dissociated graphs // Ars mathematica contemporanea. 2017. Vol. 13, no. 2. P. 293–306. doi: 10.26493/1855-3974.1013.46a
17. Allan R., Laskar R. On domination and independent domination numbers of a graph // Discret. Math. 1978. Vol. 23. P. 73–76. doi: 10.1016/0012-365X(78)90105-X
18. Зверович В.Э. Характеризация доминантно-совершенных графов // Мат. заметки. 1990. Т. 48. С. 66–69.
19. Goddard W., Henning M. Independent domination in graphs: A survey and recent results // Discret. Math. 2013. Vol. 313, no. 7. P. 839–854. doi: 10.1016/j.disc.2012.11.031
20. Zhang L., Tu J., Xin Ch. Maximum dissociation sets in subcubic trees [e-resource]. 2020. 15 p. arXiv:2005.03335. URL: https://arxiv.org/pdf/2005.03335.pdf .
21. Lokshantov D., Vatshelle M., Villanger Y.. Independent set in $P_5$-free graphs in polynomial time // Proc. of the Twenty-Fifth Annual ACM SIAM Symp. on Discrete Algorithms (SODA 2014, USA). USA: SIAM, 2014. P. 570–581. doi: 10.1137/1.9781611973402.43
22. Polynomial-time algorithm for maximum weight independent set on $P_6$-free graphs / Grzesik A. et al. // Proc. of the Thirtieth Annual ACM-SIAM Symp. on Discrete Algorithms (SODA 2019, USA). USA: SIAM, 2019. P. 1257–1271. doi: 10.1145/contrib-81508705261
23. Golumbic M., Goss C. Perfect elimination and сhordal bipartite graphs // J. Graph Theory. 1978. Vol. 2. P. 155–163. doi: 10.1002/JGT.3190020209
24. Damaschke P., MЈuller H., Kratsch D. Domination in convex and chordal bipartite graphs // Information Processing Letters. 1990. Vol. 36, no. 5. P. 231–236. doi: 10.1016/0020-0190(90)90147-P
25. Orlovich Yu., Finke G., Gordon V., Zverovich I. Approximability results for the maximum and minimum maximal induced matching problems // Discrete Optim. 2008. Vol. 5. P. 584–593. doi: 10.1016/j.disopt.2007.11.010
26. Kartynnik Yu., Ryzhikov A. On minimum maximal distance-k matchings // Discrete Math. and Theoretical Comp. Sci. 2018. Vol. 20, no. 1. doi: 10.23638/DMTCS-20-1-3
27. Lepin V. A linear algorithm for computing of a minimum weight maximal induced matching in an edge-weighted tree // Electronic Notes in Discrete Math. 2006. Vol. 24. P. 111–116. doi: 10.1016/j.endm.2006.06.019
28. Алексеев В.Е. О влиянии локальных ограничений на сложность определения числа независимости графа // Комбинаторно-алгебраические методы в прикладной математике: сб. ст. Горький: Изд-во Горьков. ун-та, 1983. С. 3–13.
29. Gartland P., Lokshtanov D. Independent set on $p_k$-free graphs in quasi-polynomial time // 61st Annual Symposium on Foundations of Comp. Sci. (FOCS): Proc. 2020 IEEE 61st Annual Symposium on FOCS. Piscataway: IEEE. P. 613–624. doi: 10.1109/FOCS46700.2020.00063
30. The maximum independent set problem in planar graphs / V.E. Alekseev et al. // Internat. Symp. on Math. Foundations of Comp. Sci. Berlin; Heidelberg: Springer, 2008. P. 96–107. (Lecture Notes in Comp. Sci.; vol 5162). doi: 10.1007/978-3-540-85238-4_7
31. Ahadi A., Dehghan A. (2/2/3)-SAT problem and its applications in dominating set problems // Discrete Mathematics & Theoretical Computer Science. 2019. Vol. 21, no. 4. Art. no. 9. 10 p. doi: 10.23638/DMTCS-21-4-9
32. Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: ИД “Вильямс”, 2016. 400 с.
Поступила 22.02.2022
После доработки 4.05.2022
Принята к публикации 11.05.2022
Дугинов Олег Иванович
канд. физ.-мат. наук
старший науч. сотрудник
Белорусский государственный университет, г. Минск
e-mail: oduginov@gmail.com
Кускова Барбара Михайловна
магистрант
Белорусский государственный университет, г. Минск
e-mail: basia.kuskova@gmail.com
Малышев Дмитрий Сергеевич
д-р физ.-мат. наук, доцент
ведущий науч. сотрудник
Лаборатория алгоритмов и технологий анализа сетевых структур
НИУ ВШЭ в Нижнем Новгороде
e-mail: dsmalyshev@rambler.ru
Шур Наталья Александровна
младший науч. сотрудник
Белорусский государственный университет, г. Минск
e-mail: linatka427@gmail.com
Ссылка на статью: О.И. Дугинов, Б.М. Кускова, Д.С. Малышев, Н.А. Шур. Структурные и алгоритмические свойства максимальных диссоциирующих множеств в графах // Тр. Ин-та математики и механики УрО РАН. 2022. Т. 28, № 2. С. 114-142
English
O.I. Duginov, B.M. Kuskova, D.S. Malyshev, N.A. Shur. Structural and algorithmic properties of maximal dissociating sets in graphs
A subset of the vertex set of a graph is called dissociating if the degrees of the vertices of the subgraph generated by this subset do not exceed 1. A dissociating set is maximal if it is not contained in any dissociating set with a greater number of vertices. Estimates for the greatest (smallest) number of vertices in a maximal dissociating set of a graph are proposed. It is proved that the problem of finding a maximal dissociating set of smallest cardinality is NP-hard for quasichordal bipartite graphs. In addition, it is proved that the problem of finding a maximal dissociating set of smallest cardinality is NP-hard for chordal bipartite graphs, bipartite graphs with the greatest degree of a vertex equal to 3, planar graphs with large girth, and for classes of graphs characterized by finite lists of forbidden generated biconnected subgraphs. A linear algorithm for solving the latter problem in the class of trees is proposed.
Keywords: maximal dissociating set of a graph, problem of finding a maximal generated subgraph with maximum degree of a vertex at most 1, maximal dissociation set, perfect elimination bipartite graph, NP-completeness, hereditary graph classes, trees
Received February 22, 2022
Revised May 4, 2022
Accepted May 11, 2022
Funding Agency: The research of the third author was supported by the Russian Foundation for Basic Research (project no. 20-51-04001). The research of the first and the fourth authors was supported by the Belarusian Republican Foundation for Fundamental Research (project no. F21RM-001).
Oleg Ivanovich Duginov, Cand. Sci. (Phys.-Math.), Belarusian State University, Minsk, 220030 Belarus, e-mail: oduginov@gmail.com
Barbara Mihajlovna Kuskova, graduate student, Belarusian State University, Minsk, 220030 Belarus, e-mail: basia.kuskova@gmail.com
Dmitrii Sergeevich Malyshev, Dr. Phys.-Math. Sci., Laboratory of Algorithms and Technologies for Networks Analysis, Higher School of Economics, Nizhny Novgorod, 603093 Russia, e-mail: dsmalyshev@rambler.ru
Natalia Aleksandrovna Shur, Belarusian State University, Minsk, 220030 Belarus, e-mail: linatka427@gmail.com
Cite this article as: O.I. Duginov, B.M. Kuskova, D.S. Malyshev, N.A. Shur. Structural and algorithmic properties of maximal dissociating sets in graphs. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2022, vol. 28, no. 2, pp. 114–142.
[References -> on the "English" button bottom right]
