The complexity of dissociation set problems in graphs. (English) Zbl 1223.68058
Summary: A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph, is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.
MSC:
| 68Q25 | Analysis of algorithms and problem complexity |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
References:
| [1] | V.E. Alekseev, On the number of maximal stable sets in graphs from hereditary classes, in: Combinatorial-Algebraic Methods in Discrete Optimization, Gor’kov. Gos. University, Gorky, 1991, pp. 5-8 (in Russian).; V.E. Alekseev, On the number of maximal stable sets in graphs from hereditary classes, in: Combinatorial-Algebraic Methods in Discrete Optimization, Gor’kov. Gos. University, Gorky, 1991, pp. 5-8 (in Russian). |
| [2] | Alekseev, V. E., Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Appl. Math., 135, 3-16 (2004) · Zbl 0931.05078 |
| [3] | Ausiello, G.; Crescenzi, P.; Gambosi, G.; Kann, V.; Marchetti-Spaccamela, A.; Protasi, M., (Complexity and Approximation. Complexity and Approximation, Combinatorial Optimization Problems and their Approximability Properties (1999), Springer: Springer Berlin) · Zbl 0937.68002 |
| [4] | Ausiello, G.; Paschos, V. Th., Reductions, completeness and the hardness of approximability, Eur. J. Oper. Res., 172, 719-739 (2006) · Zbl 1111.90092 |
| [5] | Balas, E.; Yu, C. S., On graphs with polynomially solvable maximum-weight clique problem, Networks, 19, 247-253 (1989) · Zbl 0661.05036 |
| [6] | Boliac, R.; Cameron, K.; Lozin, V., On computing the dissociation number and the induced matching number of bipartite graphs, Ars Combin., 72, 241-253 (2004) · Zbl 1075.05066 |
| [7] | Bondy, J. A.; Murty, U. S.R., Graph Theory with Applications (1976), American Elsevier Publishing Company: American Elsevier Publishing Company New York · Zbl 1134.05001 |
| [8] | Brandstädt, A.; Le, V. B.; Spinrad, J. P., (Graph Classes: A Survey. Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications (1999), SIAM: SIAM Philadelphia, PA) · Zbl 0919.05001 |
| [9] | Broersma, H.; Kloks, T.; Kratsch, D.; Müller, H., Independent sets in asteroidal triple-free graphs, SIAM J. Discrete Math., 12, 276-287 (1999) · Zbl 0918.68072 |
| [10] | Cameron, K., Induced matchings, Discrete Appl. Math., 24, 97-102 (1989) · Zbl 0687.05033 |
| [11] | Cameron, K., Induced matchings in intersection graphs, Discrete Math., 278, 1-9 (2004) · Zbl 1033.05080 |
| [12] | Cameron, K.; Hell, P., Independent packings in structured graphs, Math. Program., Ser. B, 105, 201-213 (2006) · Zbl 1078.05067 |
| [13] | Cameron, K.; Sritharan, R.; Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Math., 266, 133-142 (2003) · Zbl 1022.05064 |
| [14] | Cameron, K.; Walker, T. L., The graphs with maximum matching and maximum induced matching the same size, Discrete Math., 299, 49-55 (2005) · Zbl 1073.05054 |
| [15] | Chang, J.-M., Induced matchings in asteroidal triple-free graphs, Discrete Appl. Math., 132, 67-78 (2004) · Zbl 1029.05120 |
| [16] | Chlebík, M.; Chlebíková, J., Approximation hardness of dominating set problems, Lecture Notes in Comput. Sci., 3221, 192-203 (2004) · Zbl 1111.68782 |
| [17] | Cook, S. A., The complexity of theorem proving procedure, (Proc. 3rd Ann. ACM Symp. on Theory of Computing (1971), ACM: ACM New York), 151-158 · Zbl 0253.68020 |
| [18] | Damaschke, P.; Müller, H.; Kratsch, D., Domination in convex and chordal bipartite graphs, Inform. Process. Lett., 36, 231-236 (1990) · Zbl 0706.68055 |
| [19] | Damian-Iordache, M.; Pemmaraju, S. V., Hardness of approximating independent domination in circle graphs, Lecture Notes in Comput. Sci., 1741, 56-69 (1999) · Zbl 0971.68068 |
| [20] | De Simone, C.; Sassano, A., Stability number of bull- and chair-free graphs, Discrete Appl. Math., 41, 121-129 (1993) · Zbl 0773.05070 |
| [21] | Downey, R. G.; Fellows, M. R., (Parameterized Complexity. Parameterized Complexity, Monographs in Computer Science (1999), Springer: Springer New York) · Zbl 0914.68076 |
| [22] | Duckworth, W.; Manlove, D.; Zito, M., On the approximability of the maximum induced matching problem, J. Discrete Algorithms, 3, 79-91 (2005) · Zbl 1075.68063 |
| [23] | Favaron, O., On a conjecture of Fink and Jacobson concerning \(k\)-domination and \(k\)-dependence, J. Combin. Theory Ser. B, 39, 101-102 (1985) · Zbl 0583.05049 |
| [24] | Favaron, O., \(k\)-domination and \(k\)-dependence in graphs, Ars. Combin., 250, 159-167 (1988) · Zbl 0820.05041 |
| [25] | Garey, M. R.; Johnson, D. S., Computers and Intractability. A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Co.: W.H. Freeman and Co. San Francisco, CA · Zbl 0411.68039 |
| [26] | Gavril, F., Algorithms for minimum coloring, maximum clique, minimum coverings by cliques, and maximum independent set of a chordal graph, SIAM J. Comput., 1, 180-187 (1972) · Zbl 0227.05116 |
| [27] | Gavril, F., Maximum weight independent sets and cliques in intersection graphs of filaments, Inform. Process. Lett., 73, 181-188 (2000) · Zbl 1339.05287 |
| [28] | Golumbic, M. C.; Goss, C. F., Perfect elimination and chordal bipartite graphs, J. Graph Theory, 2, 155-163 (1978) · Zbl 0411.05060 |
| [29] | Golumbic, M. C.; Laskar, R., Irredundancy in circular arc graphs, Discrete Appl. Math., 44, 79-89 (1993) · Zbl 0783.05059 |
| [30] | Grötschel, M.; Lovász, L.; Schrijver, A., Polynomial algorithms for perfect graphs, Ann. Discrete Math., 21, 325-356 (1984) · Zbl 0554.05041 |
| [31] | Halldórsson, M. M., Approximations of independent sets in graphs, Lecture Notes in Comput. Sci., 1444, 1-13 (1998) · Zbl 0903.05044 |
| [32] | Halldórsson, M. M., Approximating the minimum maximal independence number, Inform. Process. Lett., 47, 169-172 (1993) · Zbl 0778.68041 |
| [33] | Halldórsson, M. M.; Radhakrishnan, J., Greed is good: approximating independent sets in sparse and bounded-degree graphs, Algorithmica, 18, 143-163 (1997) · Zbl 0866.68077 |
| [34] | Harary, F.; Holzmann, C., Line graphs of bipartite graphs, Rev. Soc. Mat. Chile, 1, 19-20 (1974) |
| [35] | Havet, F.; Kang, R. J.; Sereni, J.-S., Improper colouring of unit disk graphs, Networks, 54, 150-164 (2009) · Zbl 1207.05056 |
| [36] | Hayward, R. B., Weakly triangulated graphs, J. Combin. Theory Ser. B, 39, 200-208 (1985) · Zbl 0551.05055 |
| [37] | Hayward, R. B.; Hoáng, C. T.; Maffray, F., Optimizing weakly triangulated graphs, Graphs Combin., 5, 339-349 (1989) · Zbl 0679.68082 |
| [38] | Håstad, J., Clique is hard to approximate within \(n^{1 - \varepsilon}\), Acta Math., 182, 105-142 (1999) · Zbl 0989.68060 |
| [39] | Irving, R. W., On approximating the minimum independent dominating set, Inform. Process. Lett., 37, 197-200 (1991) · Zbl 0713.68033 |
| [40] | Kirkpatrick, D. G.; Hell, P., On the complexity of a generalized matching problem, (Proc. 10th Ann. ACM Symp. on Theory of Computing (1978), ACM: ACM New York), 240-245 · Zbl 1282.68182 |
| [41] | Kirkpatrick, D. G.; Hell, P., On the complexity of general graph factor problems, SIAM J. Comput., 12, 601-609 (1983) · Zbl 0525.68023 |
| [42] | Kobler, D.; Rotics, U., Finding maximum induced matchings in subclasses of claw-free and \(P_5\)-free graphs, and in graphs with matching and induced matching of equal maximum size, Algorithmica, 37, 327-346 (2003) · Zbl 1082.68592 |
| [43] | Ko, C. W.; Shepherd, F. B., Bipartite domination and simultaneous matroid covers, SIAM J. Discrete Math., 16, 517-523 (2003) · Zbl 1029.05097 |
| [44] | Lehot, P. G.H., An optimal algorithm to detect a line graph and output its root graph, J. Assoc. Comput. Mach., 21, 569-575 (1974) · Zbl 0295.05118 |
| [45] | Lozin, V. V., On maximum induced matchings in bipartite graphs, Inform. Process. Lett., 81, 7-11 (2002) · Zbl 1046.68081 |
| [46] | Lozin, V. V.; Milanič, M., A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, J. Discrete Algorithms, 6, 595-604 (2008) · Zbl 1154.90607 |
| [47] | Lozin, V.; Mosca, R., Maximum independent sets in subclasses of \(P_5\)-free graphs, Inform. Process. Lett., 109, 319-324 (2009) · Zbl 1189.05136 |
| [48] | Lozin, V.; Rautenbach, D., Some results on graphs without long induced paths, Inform. Process. Lett., 88, 167-171 (2003) · Zbl 1178.68285 |
| [49] | Masuda, S.; Nakajima, K., An optimal algorithm for finding a maximum independent set of a circular-arc graph, SIAM J. Comput., 17, 41-52 (1988) · Zbl 0646.68084 |
| [50] | Minty, G. J., On maximal independent sets of vertices in claw-free graphs, J. Combin. Theory Ser. B, 28, 284-304 (1980) · Zbl 0434.05043 |
| [51] | Müller, H., Hamiltonian circuits in chordal bipartite graphs, Discrete Math., 156, 291-298 (1996) · Zbl 0856.68113 |
| [52] | Müller, H.; Brandstädt, A., The NP-completeness of steiner tree and dominating set for chordal bipartite graphs, Theoret. Comput. Sci., 53, 257-265 (1987) · Zbl 0638.68062 |
| [53] | Murphy, O. J., Computing independent sets in graphs with large girth, Discrete Appl. Math., 35, 167-170 (1992) · Zbl 0769.05053 |
| [54] | Nakamura, D.; Tamura, A., A revision of Minty’s algorithm for finding a maximum weight stable set in a claw-free graph, J. Oper. Res. Soc. Japan, 44, 194-204 (2001) · Zbl 1128.05318 |
| [55] | Orlovich, Yu.; Finke, G.; Gordon, V.; Zverovich, I., Approximability results for the maximum and minimum maximal induced matching problems, Discrete Optim., 5, 584-593 (2008) · Zbl 1140.90479 |
| [56] | Orlovich, Yu. L.; Gordon, V. S.; de Werra, D., On the inapproximability of independent domination in \(2 P_3\)-free perfect graphs, Theoret. Comput. Sci., 410, 977-982 (2009) · Zbl 1162.68027 |
| [57] | Yu.L. Orlovich, I.E. Zverovich, Maximal induced matchings of minimum/maximum size, DIMACS TR 2004-26, 2004.; Yu.L. Orlovich, I.E. Zverovich, Maximal induced matchings of minimum/maximum size, DIMACS TR 2004-26, 2004. |
| [58] | Papadimitriou, C. H.; Yannakakis, M., The complexity of restricted spanning tree problems, J. Assoc. Comput. Mach., 29, 285-309 (1982) · Zbl 0478.68068 |
| [59] | Poljak, S., A note on stable sets and coloring of graphs, Comment. Math. Univ. Carolin., 15, 307-309 (1974) · Zbl 0284.05105 |
| [60] | Sbihi, N., Algorithme de recherche d’un stable de cardinalité maximum dans un graphe sans étoile, Discrete Math., 29, 53-76 (1980) · Zbl 0444.05049 |
| [61] | Sedláček, J., Some properties of interchange graphs, (Theory of Graphs and its Applications (1962), Academic Press: Academic Press New York), 145-150 · Zbl 0156.44202 |
| [62] | Spinrad, J. P.; Sritharan, R., Algorithms for weakly triangulated graphs, Discrete Appl. Math., 19, 181-191 (1995) · Zbl 0827.68084 |
| [63] | Stockmeyer, L. J.; Vazirani, V. V., NP-completeness of some generalizations of the maximum matching problem, Inform. Process. Lett., 15, 14-19 (1982) · Zbl 0493.68039 |
| [64] | Tsukiyama, S.; Ide, M.; Ariyoshi, H.; Shirakawa, I., A new algorithm for generating all maximal independent sets, SIAM J. Comput., 6, 505-517 (1977) · Zbl 0364.05027 |
| [65] | Whitney, H., Congruent graphs and the connectivity of graphs, Amer. J. Math., 54, 150-168 (1932) · JFM 58.0609.01 |
| [66] | Yannakakis, M., Node-deletion problems on bipartite graphs, SIAM J. Comput., 10, 310-327 (1981) · Zbl 0468.05044 |
| [67] | Zuckerman, D., Linear degree extractors and the inapproximability of max clique and chromatic number, Theory Comput., 3, 103-138 (2007) · Zbl 1213.68322 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
