O.I. Duginov, B.M. Kuskova, D.S. Malyshev, N.A. Shur. Structural and algorithmic properties of maximal dissociating sets in graphs ... P. 114-142

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

REFERENCES

1.   Emelichev V.A., Mel’nikov O.I., Sarvanov V.I., and Tyshkevich R.I. Lectures on graph theory. Mannheim: Wissenschaftsverlag, 1994, 371 p. ISBN: 3411171219 . Original Russian text published in Emelichev V.A. et al. Lektsii po teorii grafov: uchebnoe posobie. Moscow: Librokom Publ., 2009, 392 p.

2.   McLaughlan B., Akkaya K. Coverage-based clustering of wireless sensor and actor networks. IEEE Internat. Conf. on Pervasive Services, 2007, pp. 45–54. doi: 10.1109/PERSER.2007.4283888 

3.   Yannakakis M. Node-deletion problems on bipartite graphs. SIAM J. Comput., 2006, vol. 10, no. 2, pp. 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, pp. 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.   Orlovich Y., Dolgui A., Finke G., Gordon V., Werner F. The complexity of dissociation set problems in graphs. Discret. Appl. Math., 2011, vol. 159, no. 13, pp. 1352–1366. doi: 10.1016/j.dam.2011.04.023 

7.   Cameron K., Hell P. Independent packings in structured graphs. Math. Programming, 2006, vol. 105, no. 2, pp. 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, pp. 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, pp. 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, pp. 86–97. doi: 10.1016/j.tcs.2016.04.043 

11.   Chang M.-S. et al. Moderately exponential time algorithms for the maximum bounded-degree-1 set problem. Discret. Appl. Math., 2018, vol. 251, pp. 114–125. doi: 10.1016/j.dam.2018.05.032 

12.   Betzler N. et al. On bounded-degree vertex deletion parameterized by treewidth. Discret. Appl. Math., 2012, vol. 160, no. 1-2, pp. 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, pp. 297–336. doi: 10.1007/s00453-020-00758-8 

14.   Orlovich Y.L. et al. Complexity of dissociate set problems in some hereditary classes of graphs. Dokl. Nats. Akad. Nauk Belarusi, 2009, vol. 53, no. 3, pp. 16–20. (in Russian)

15.   Tu J., Zhang Z., Shi Y. The maximum number of maximum dissociation sets in trees. J. Graph Theory, 2020, vol. 96, no. 4, pp. 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, pp. 293–306. doi: 10.26493/1855-3974.1013.46a 

17.   Allan R.B., Laskar R. On domination and independent domination numbers of a graph. Discret. Math., 1978, vol. 23, pp. 73–76. doi: 10.1016/0012-365X(78)90105-X 

18.   Zverovich V.E. Domination-complete graphs. Mathematical notes of the Academy of Sciences of the USSR, 1990, vol. 48, no. 3, pp. 920–922. doi: 10.1007/BF01157434 

19.   Goddard W., Henning M.A. Independent domination in graphs: A survey and recent results. Discret. Math., 2013, vol. 313, no. 7, pp. 839–854. doi: 10.1016/j.disc.2012.11.031 

20.   Zhang L., Tu J., Xin Ch. Maximum dissociation sets in subcubic trees. arXiv:2005.03335, 2020, 15 p. Available on: 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 Symposium on Discrete Algorithms (SODA 2014, USA), USA: SIAM, 2014, pp. 570–581. doi: 10.1137/1.9781611973402.43 

22.   Grzesik A. et al. Polynomial-time algorithm for maximum weight independent set on $P_6$-free graphs. Proc. of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019, USA), USA: SIAM, 2019, pp. 1257–1271. doi: 10.1145/contrib-81508705261 

23.   Golumbic M., Goss C.F. Perfect elimination and chordal bipartite graphs. J. Graph Theory, 1978, vol. 2, pp. 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, pp. 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. Discret. Optim., 2008, vol. 5, pp. 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, pp. 111–116. doi: 10.1016/j.endm.2006.06.019 

28.   Alekseev V.E. On the local restrictions effect on the complexity of finding the graph independence number. In: Kombinatorno-Algebraicheskie Metody v Prikladnoi Matematike. Gorkii: Gorkii Univ. Press, 1983, pp. 3–13 (in Russian).

29.   Gartland P., Lokshtanov D. Independent set on $P_k$-free graphs in quasi-polynomial time. In: Proceedings of 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS). Piscataway: IEEE, 2020, pp. 613–624. doi: 10.1109/FOCS46700.2020.00063 

30.   Alekseev V.E. et al. The maximum independent set problem in planar graphs. In: Internat. Symp. on Math. Foundations of Comp. Sci, Ser. Lecture Notes in Comp. Sci., vol. 5162. Berlin; Heidelberg: Springer, 2008, pp. 96–107. 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.   Aho A.V., Hopcroft J.E., Ullman J.D. Data structures and algorithms. Reading, Mass.: Addison-Wesley, 1983, 427 p. ISBN: 0201000237 . Translated to Russian under the title Struktury dannykh i algoritmy. Moscow: Vil’yams Publ., 2016, 400 p.

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.