Geodesic
Structural and algorithmic properties of maximal dissociating sets in graphs
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 114-142
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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, perfect elimination bipartite graph, NP-completeness, hereditary graph classes, trees.
Mots-clés : maximal dissociation set 
@article{TIMM_2022_28_2_a9,
     author = {O. I. Duginov and B. M. Kuskova and D. S. Malyshev and N. A. Shur},
     title = {Structural and algorithmic properties of maximal dissociating sets in graphs},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {114--142},
     year = {2022},
     volume = {28},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/}
}
TY  - JOUR
AU  - O. I. Duginov
AU  - B. M. Kuskova
AU  - D. S. Malyshev
AU  - N. A. Shur
TI  - Structural and algorithmic properties of maximal dissociating sets in graphs
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2022
SP  - 114
EP  - 142
VL  - 28
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/
LA  - ru
ID  - TIMM_2022_28_2_a9
ER  - 
%0 Journal Article
%A O. I. Duginov
%A B. M. Kuskova
%A D. S. Malyshev
%A N. A. Shur
%T Structural and algorithmic properties of maximal dissociating sets in graphs
%J Trudy Instituta matematiki i mehaniki
%D 2022
%P 114-142
%V 28
%N 2
%U http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/
%G ru
%F TIMM_2022_28_2_a9
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 mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 2, pp. 114-142. http://geodesic.mathdoc.fr/item/TIMM_2022_28_2_a9/

[1] V.A. Emelichev [i dr.], Lektsii po teorii grafov, uchebnoe posobie, KD “Librokom”, M., 2009, 392 pp.

[2] McLaughlan B., Akkaya K., “Coverage-based Clustering of Wireless Sensor and Actor Networks”, IEEE Internat. Conf. on Pervasive Services, 2007, 45–54 | DOI

[3] Yannakakis M., “Node-Deletion Problems on Bipartite Graphs”, SIAM J. Comp., 10:2 (1981), 310–327 | DOI | MR | Zbl

[4] Boliac R., Cameron K., Lozin V., “On computing the dissociation number and the induced matching number of bipartite graphs”, Ars Combinatoria, 72 (2004), 241–253 | MR | Zbl

[5] Boliac R., Lozin V., “On computing the dissociation number of bipartite graphs”, Rutcor research report, 2001, 31-2001, 10 pp.

[6] Yu. Orlovich et. al, “The complexity of dissociation set problems in graphs”, Discrete Appl. Math., 159:13 (2011), 1352–1366 | DOI | MR | Zbl

[7] Cameron K., Hell P., “Independent packings in structured graphs”, Math. Programming, series B, 105:2 (2006), 201–213 | DOI | MR | Zbl

[8] Lozin V., Rautenbach D., “Some results on graphs without long induced paths”, Inf. Process. Lett., 88 (2003), 167–171 | DOI | MR | Zbl

[9] Kardoš F., Katrenič J., Schiermeyer I., “On computing the minimum 3-path vertex cover and dissociation number of graphs”, Theoretical Comp. Sci., 412:50 (2011), 7009–7017 | DOI | MR | Zbl

[10] Xiao M., Kou S., “Exact algorithms for the maximum dissociation set and minimum 3-path vertex cover problems”, Theoretical Comp. Sci., 657, Part A. (2017), 86–97 | DOI | MR | Zbl

[11] M.-S. Chang et al., “Moderately exponential time algorithms for the maximum bounded-degree-1 set problem”, Discret. Appl. Math., 251 (2018), 114–125 | DOI | MR | Zbl

[12] N. Betzler et al., “On bounded-degree vertex deletion parameterized by treewidth”, Discret. Appl. Math., 160:1–2 (2012), 53–60 | DOI | MR | Zbl

[13] Ganian R., Klute F., Ordyniak S., “On structural parameterizations of the bounded-degree vertex deletion problem”, Algorithmica, 83:1 (2021), 297–336 | DOI | MR | Zbl

[14] Yu. L. Orlovich i dr., “Slozhnost zadach o dissotsiiruyuschikh mnozhestvakh v nekotorykh nasledstvennykh klassakh grafov”, Dokl. Natsional. Nauk Belarusi, 53:3 (2009), 16–20 | MR | Zbl

[15] Tu J., Zhang Z., Shi Y., “The maximum number of maximum dissociation sets in trees”, J. Graph Theory, 96:4 (2020), 472–489 | DOI | MR

[16] Brešar B., Hartnell B., Rall D., “Uniformly dissociated graphs”, Ars mathematica contemporanea, 13:2 (2017), 293–306 | DOI | MR | Zbl

[17] Allan R., Laskar R., “On domination and independent domination numbers of a graph”, Discret. Math., 23 (1978), 73–76 | DOI | MR | Zbl

[18] Zverovich V.E., “Kharakterizatsiya dominantno-sovershennykh grafov”, Mat. zametki, 48 (1990), 66–69

[19] Goddard W., Henning M., “Independent domination in graphs: A survey and recent results”, Discret. Math., 313:7 (2013), 839–854 | DOI | MR | Zbl

[20] Zhang L., Tu J., Xin Ch., Maximum dissociation sets in subcubic trees, [e-resource], 2020, 15 pp., arXiv: 2005.03335

[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)), SIAM, USA, 2014, 570–581 | DOI | MR | Zbl

[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 Symp. on Discrete Algorithms ((SODA 2019, USA)), SIAM, USA, 2019, 1257–1271 | DOI | MR | Zbl

[23] Golumbic M., Goss C., “Perfect elimination and shordal bipartite graphs”, J. Graph Theory, 2 (1978), 155–163 | DOI | MR

[24] Damaschke P., Müller H., Kratsch D., “Domination in convex and chordal bipartite graphs”, Information Processing Letters, 36:5 (1990), 231–236 | DOI | MR | Zbl

[25] Orlovich Yu., Finke G., Gordon V., Zverovich I., “Approximability results for the maximum and minimum maximal induced matching problems”, Discrete Optim., 5 (2008), 584–593 | DOI | MR | Zbl

[26] Kartynnik Yu., Ryzhikov A., “On minimum maximal distance-k matchings”, Discrete Math. and Theoretical Comp. Sci., 20:1 (2018) | DOI | MR | Zbl

[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., 24 (2006), 111–116 | DOI | MR | Zbl

[28] Alekseev V.E., “O vliyanii lokalnykh ogranichenii na slozhnost opredeleniya chisla nezavisimosti grafa”, Kombinatorno-algebraicheskie metody v prikladnoi matematike, sb. st., Izd-vo Gorkov. un-ta, Gorkii, 1983, 3–13 | MR

[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, IEEE, Piscataway, 613–624 | DOI | MR

[30] V.E. Alekseev et al., “The maximum independent set problem in planar graphs”, Internat. Symp. on Math. Foundations of Comp. Sci., Lecture Notes in Comp. Sci., 5162, Springer, Berlin; Heidelberg, 2008, 96–107 | DOI | MR | Zbl

[31] Ahadi A., Dehghan A., “$(2/2/3)$-SAT problem and its applications in dominating set problems”, Discrete Mathematics Theoretical Computer Science, 21:4 (2019), 9, 10 pp. | DOI | MR | Zbl

[32] Akho A., Khopkroft Dzh., Ulman Dzh., Struktury dannykh i algoritmy, ID “Vilyams”, M., 2016, 400 pp.