Efficient domination and efficient edge domination: a brief survey. (English) Zbl 1400.05170
Panda, B. S. (ed.) et al., Algorithms and discrete applied mathematics. 4th international conference, CALDAM 2018, Guwahati, India, February 15–17, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-74179-6/pbk; 978-3-319-74180-2/ebook). Lecture Notes in Computer Science 10743, 1-14 (2018).
Summary: In a finite undirected graph \(G=(V,E)\), a vertex \(v\in V\) dominates itself and its neighbors in \(G\). A vertex set \(D\subseteq V\) is an efficient dominating set (e.d.s. for short) of \(G\) if every \(v\in V\) is dominated in \(G\) by exactly one vertex of \(D\).{
}
The Efficient Domination (ED) problem, which asks for the existence of an e.d.s. in \(G\), is known to be \(\mathbb{NP}\)-complete for bipartite graphs, for (very special) chordal graphs and for line graphs but solvable in polynomial time for many subclasses. For \(H\)-free graphs, a dichotomy of the complexity of ED has been reached.{
}
An edge set \(M\subseteq E\) is an efficient edge dominating set (e.e.d.s. for short) of \(G\) if every \(e\in E\) is dominated in \(G\) by exactly one edge of \(M\) with respect to the line graph \(L(G)\). Thus, \(M\) is an e.e.d.s. in \(G\) if and only if \(M\) is an e.d.s. in \(L(G)\). An e.e.d.s. is called dominating induced matching in various papers.{
}
The Efficient Edge Domination (EED) problem, which asks for the existence of an e.e.d.s. in \(G\), is known to be \(\mathbb{NP}\)-complete even for special bipartite graphs but solvable in polynomial time for various graph classes. The problems ED and EED are based on the \(\mathbb{NP}\)-complete Exact Cover problem on hypergraphs.
For the entire collection see [Zbl 1382.68013].
For the entire collection see [Zbl 1382.68013].
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 68R10 | Graph theory (including graph drawing) in computer science |
References:
| [1] | Bange, DW; Barkauskas, AE; Slater, PJ; Ringeisen, RD; Roberts, FS, Efficient dominating sets in graphs, Applications of Discrete Mathematics, 189-199, 1988, Philadelphia: SIAM, Philadelphia · Zbl 0664.05027 |
| [2] | Bange, DW; Barkauskas, AE; Host, LH; Slater, PJ, Generalized domination and efficient domination in graphs, Discrete Math., 159, 1-11, 1996 · Zbl 0860.05044 · doi:10.1016/0012-365X(95)00094-D |
| [3] | Biggs, N., Perfect codes in graphs, J. Comb. Theory Ser. B, 15, 289-296, 1973 · Zbl 0256.94009 · doi:10.1016/0095-8956(73)90042-7 |
| [4] | Brandstädt, A.: Weighted efficient domination for \(P_5\)-free graphs in linear time. CoRR arXiv:1507.06765v1 (2015) |
| [5] | Brandstädt, A.; Chepoi, VD; Dragan, FF, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Discrete Appl. Math., 82, 43-77, 1998 · Zbl 0893.05018 · doi:10.1016/S0166-218X(97)00125-X |
| [6] | Brandstädt, A.; Dragan, FF; Chepoi, VD; Voloshin, VI, Dually chordal graphs, SIAM J. Discrete Math., 11, 437-455, 1998 · Zbl 0909.05037 · doi:10.1137/S0895480193253415 |
| [7] | Brandstädt, A., Eschen, E.M., Friese, E.: Efficient domination for some subclasses of \(P_6\)-free graphs in polynomial time. CoRR arXiv:1503.00091 (2015). Extended abstract. In: Mayr, E.W. (ed.) Proceedings of WG 2015. LNCS, vol. 9224, pp. 78-89 (2015) · Zbl 1417.05150 |
| [8] | Brandstädt, A.; Eschen, EM; Friese, E.; Karthick, T., Efficient domination for classes of \(P_6\)-free graphs, Discrete Appl. Math., 223, 15-27, 2017 · Zbl 1476.05151 · doi:10.1016/j.dam.2016.08.019 |
| [9] | Brandstädt, A.; Fičur, P.; Leitert, A.; Milanič, M., Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs, Inf. Process. Lett., 115, 256-262, 2015 · Zbl 1304.05104 · doi:10.1016/j.ipl.2014.09.024 |
| [10] | Brandstädt, A., Giakoumakis, V.: Weighted efficient domination for \((P_5+kP_2)\)-free graphs in polynomial time. CoRR arXiv:1407.4593v1 (2014) |
| [11] | Brandstädt, A., Giakoumakis, V., Milanič, M., Nevries, R.: Weighted efficient domination for \(F\)-free graphs. Manuscript (2014, submitted) |
| [12] | Brandstädt, A.; Hoàng, CT, Maximum induced matchings for chordal graphs in linear time, Algorithmica, 52, 440-447, 2008 · Zbl 1171.68595 · doi:10.1007/s00453-007-9045-2 |
| [13] | Brandstädt, A.; Hundt, C.; Nevries, R.; López-Ortiz, A., Efficient edge domination on hole-free graphs in polynomial time, LATIN 2010: Theoretical Informatics, 650-661, 2010, Heidelberg: Springer, Heidelberg · Zbl 1283.05197 · doi:10.1007/978-3-642-12200-2_56 |
| [14] | Brandstädt, A.; Karthick, T., Weighted efficient domination in two subclasses of \(P_6\)-free graphs, Discrete Appl. Math., 201, 38-46, 2016 · Zbl 1329.05225 · doi:10.1016/j.dam.2015.07.032 |
| [15] | Brandstädt, A.; Le, VB; Spinrad, JP, Graph Classes: A Survey, 1999, Philadelphia: SIAM, Philadelphia · Zbl 0919.05001 · doi:10.1137/1.9780898719796 |
| [16] | Brandstädt, A.; Leitert, A.; Rautenbach, D.; Chao, K-M; Hsu, T.; Lee, D-T, Efficient dominating and edge dominating sets for graphs and hypergraphs, Algorithms and Computation, 267-277, 2012, Heidelberg: Springer, Heidelberg · Zbl 1260.05108 · doi:10.1007/978-3-642-35261-4_30 |
| [17] | Brandstädt, A.; Milanič, M.; Nevries, R.; Chatterjee, K.; Sgall, J., New polynomial cases of the weighted efficient domination problem, Mathematical Foundations of Computer Science 2013, 195-206, 2013, Heidelberg: Springer, Heidelberg · Zbl 1398.68218 · doi:10.1007/978-3-642-40313-2_19 |
| [18] | Brandstädt, A.; Mosca, R.; Asano, T.; Nakano, S.; Okamoto, Y.; Watanabe, O., Dominating induced matchings for \(P_7\)-free graphs in linear time, Algorithms and Computation, 100-109, 2011, Heidelberg: Springer, Heidelberg · Zbl 1349.05249 · doi:10.1007/978-3-642-25591-5_12 |
| [19] | Brandstädt, A., Mosca, R.: Weighted efficient domination for \(P_6\)-free graphs in polynomial time. CoRR arXiv:1508.07733 (2015). Based on a manuscript by R. Mosca, Weighted Efficient Domination for \(P_6\)-Free Graphs, July 2015 |
| [20] | Brandstädt, A.; Mosca, R.; Heggernes, P., Weighted efficient domination for \(P_6\)-free and for \(P_5\)-free graphs, Graph-Theoretic Concepts in Computer Science, 38-49, 2016, Heidelberg: Springer, Heidelberg · Zbl 1417.05151 · doi:10.1007/978-3-662-53536-3_4 |
| [21] | Brandstädt, A.; Mosca, R., Dominating induced matchings for \(P_8\)-free graphs in polynomial time, Algorithmica, 77, 1283-1302, 2017 · Zbl 1360.68497 · doi:10.1007/s00453-016-0150-y |
| [22] | Brandstädt, A., Mosca, R.: On efficient domination for some classes of \(H\)-free chordal graphs. CoRR arXiv:1701.03414 (2017). Extended abstract in Conference Proceedings of LAGOS 2017, Marseille, Electron. Notes Discrete Math. 62, 57-62 (2017) · Zbl 1383.05229 |
| [23] | Brandstädt, A., Mosca, R.: Dominating induced matchings in \(S_{1,2,4}\)-free graphs. CoRR arXiv:1706.09301 (2017) |
| [24] | Broersma, HJ; 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 · doi:10.1137/S0895480197326346 |
| [25] | Cameron, K., Induced matchings, Discrete Appl. Math., 24, 97-102, 1989 · Zbl 0687.05033 · doi:10.1016/0166-218X(92)90275-F |
| [26] | Cameron, K., Induced matchings in intersection graphs, Discrete Math., 278, 1-9, 2004 · Zbl 1033.05080 · doi:10.1016/j.disc.2003.05.001 |
| [27] | Cameron, K.; Sritharan, R.; Tang, Y., Finding a maximum induced matching in weakly chordal graphs, Discrete Math., 266, 133-142, 2003 · Zbl 1022.05064 · doi:10.1016/S0012-365X(02)00803-8 |
| [28] | Cardoso, DM; Cerdeira, JO; Delorme, C.; Silva, PC, Efficient edge domination in regular graphs, Discrete Appl. Math., 156, 3060-3065, 2008 · Zbl 1210.05094 · doi:10.1016/j.dam.2008.01.021 |
| [29] | Cardoso, DM; Korpelainen, N.; Lozin, VV, On the complexity of the dominating induced matching problem in hereditary classes of graphs, Discrete Appl. Math., 159, 521-531, 2011 · Zbl 1213.05206 · doi:10.1016/j.dam.2010.03.011 |
| [30] | Cardoso, DM; Lozin, VV; Lipshteyn, M.; Levit, VE; McConnell, RM, Dominating induced matchings, Graph Theory, Computational Intelligence and Thought, 77-86, 2009, Heidelberg: Springer, Heidelberg · Zbl 1194.05114 · doi:10.1007/978-3-642-02029-2_8 |
| [31] | Chang, M-S, Weighted domination of co-comparability graphs, Discrete Appl. Math., 80, 135-148, 1997 · Zbl 0898.05077 · doi:10.1016/S0166-218X(97)80001-7 |
| [32] | Chang, J-M, Induced matchings in asteroidal-triple-free graphs, Discrete Appl. Math., 132, 67-78, 2004 · Zbl 1029.05120 · doi:10.1016/S0166-218X(03)00390-1 |
| [33] | Chang, J-M; Ho, C-W; Ko, M-T, Powers of asteroidal-triple-free graphs with applications, Ars Comb., 67, 161-173, 2003 · Zbl 1073.05566 |
| [34] | Chang, M-S; Liu, YC, Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs, Inf. Process. Lett., 48, 205-210, 1993 · Zbl 0787.68077 · doi:10.1016/0020-0190(93)90147-2 |
| [35] | Chang, M-S; Liu, YC, Polynomial algorithms for the weighted perfect domination problems on interval and circular-arc graphs, J. Inf. Sci. Eng., 11, 549-568, 1994 |
| [36] | Chang, GJ; Pandu Rangan, C.; Coorg, SR, Weighted independent perfect domination on co-comparability graphs, Discrete Appl. Math., 63, 215-222, 1995 · Zbl 0848.05039 · doi:10.1016/0166-218X(94)00067-3 |
| [37] | Chudnovsky, M.; Robertson, N.; Seymour, P.; Thomas, R., The strong perfect graph theorem, Ann. Math., 164, 51-229, 2006 · Zbl 1112.05042 · doi:10.4007/annals.2006.164.51 |
| [38] | Courcelle, B.; Makowsky, JA; Rotics, U., Linear time solvable optimization problems on graphs of bounded clique-width, Theory Comput. Syst., 33, 125-150, 2000 · Zbl 1009.68102 · doi:10.1007/s002249910009 |
| [39] | Dragan, FF; Prisacaru, CF; Chepoi, VD, Location problems in graphs and the Helly property, Discrete Math., 4, 67-73, 1992 · Zbl 0804.05067 |
| [40] | Edmonds, J., Paths, trees, and flowers, Canad. J. Math., 17, 449-467, 1965 · Zbl 0132.20903 · doi:10.4153/CJM-1965-045-4 |
| [41] | Eschen, E.; Wang, X., Algorithms for unipolar and generalized split graphs, Discrete Appl. Math., 162, 195-201, 2014 · Zbl 1300.05251 · doi:10.1016/j.dam.2013.08.011 |
| [42] | Fellows, MR; Hoover, MN, Perfect domination, Australas. J. Comb., 3, 141-150, 1991 · Zbl 0761.05091 |
| [43] | Flotow, C., On powers of \(m\)-trapezoid graphs, Discrete Appl. Math., 63, 187-192, 1995 · Zbl 0839.05091 · doi:10.1016/0166-218X(95)00062-V |
| [44] | Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the 5th British Combinatorial Conference (Aberdeen 1975), Congressus Numerantium, No. XV, pp. 211-226 (1976) · Zbl 0328.05141 |
| [45] | Fricke, G.; Laskar, R., Strong matchings on trees, Congr. Numer., 89, 239-243, 1992 · Zbl 0786.05065 |
| [46] | Friese, E.: Das Efficient-Domination-Problem auf \(P_6\)-freien Graphen. Master thesis. University of Rostock, Germany (2013). (in German) |
| [47] | Garey, MR; Johnson, DS, Computers and Intractability - A Guide to the Theory of NP-completeness, 1979, San Francisco: Freeman, San Francisco · Zbl 0411.68039 |
| [48] | Gavril, F., Maximum weight independent sets and cliques in intersection graphs of filaments, Inf. Process. Lett., 73, 181-188, 2000 · Zbl 1339.05287 · doi:10.1016/S0020-0190(00)00025-9 |
| [49] | Golumbic, MC; Laskar, R., Irredundancy in circular arc graphs, Discrete Appl. Math., 44, 79-89, 1993 · Zbl 0783.05059 · doi:10.1016/0166-218X(93)90223-B |
| [50] | Golumbic, MC; Lewenstein, M., New results on induced matchings, Discrete Appl. Math., 101, 157-165, 2000 · Zbl 0951.68104 · doi:10.1016/S0166-218X(99)00194-8 |
| [51] | Grinstead, DL; Slater, PL; Sherwani, NA; Holmes, ND, Efficient edge domination problems in graphs, Inf. Process. Lett., 48, 221-228, 1993 · Zbl 0797.05076 · doi:10.1016/0020-0190(93)90084-M |
| [52] | Grötschel, M.; Lovász, L.; Schrijver, A., The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1, 169-197, 1981 · Zbl 0492.90056 · doi:10.1007/BF02579273 |
| [53] | Hayward, R.B., Spinrad, J.P., Sritharan, R.: Weakly chordal graph algorithms via handles. In: Proceedings of the 11th Symposium on Discrete Algorithms (SODA), pp. 42-49 (2000) · Zbl 0956.68104 |
| [54] | Hayward, R.B., Spinrad, J.P., Sritharan, R.: Improved algorithms for weakly chordal graphs. ACM Trans. Algorithms 3, Article No. 14 (2007) · Zbl 1321.05265 |
| [55] | Hertz, A., Lozin, V.V., Ries, B., Zamaraev, V., de Werra, D.: Dominating induced matchings in graphs containing no long claw. CoRR arXiv:1505.02558 (2015) |
| [56] | Karp, RM; Miller, RE; Thatcher, JW; Bohlinger, JD, Reducibility among combinatorial problems, Complexity of Computer Computations, 85-103, 1972, New York: Plenum Press, New York · Zbl 1467.68065 · doi:10.1007/978-1-4684-2001-2_9 |
| [57] | Karthick, T.; Ganguly, S.; Krishnamurti, R., New polynomial case for efficient domination in \(P_6\)-free graphs, Algorithms and Discrete Applied Mathematics, 81-88, 2015, Cham: Springer, Cham · Zbl 1432.68182 |
| [58] | 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 · doi:10.1007/s00453-003-1035-4 |
| [59] | Köhler, E.: Graphs without asteroidal triples. Ph.D. thesis, Technical University of Berlin (1999) |
| [60] | Korpelainen, N.; Lozin, VV; Purcell, C., Dominating induced matchings in graphs without a skew star, J. Discrete Algorithms, 26, 45-55, 2014 · Zbl 1298.05253 · doi:10.1016/j.jda.2013.11.002 |
| [61] | Kratochvíl, J.: Perfect codes in general graphs, Rozpravy Československé Akad. Věd Řada Mat. Přírod \(V{\rm \check{d}} 7\). Akademia, Praha (1991) · Zbl 0858.94024 |
| [62] | Kratochvíl, J., Regular codes in regular graphs are difficult, Discrete Math., 133, 191-205, 1994 · Zbl 0821.68096 · doi:10.1016/0012-365X(94)90026-4 |
| [63] | Krishnamurthy, CM; Sritharan, R., Maximum induced matching problem on HHD-free graphs, Discrete Appl. Math., 160, 224-230, 2012 · Zbl 1237.05166 · doi:10.1016/j.dam.2011.08.027 |
| [64] | Leitert, A.: Das dominating induced matching problem für azyklische Hypergraphen. Diploma thesis, University of Rostock, Germany (2012) |
| [65] | Liang, YD; Lu, CL; Tang, CY; Jiang, T.; Lee, DT, Efficient domination on permutation graphs and trapezoid graphs, Computing and Combinatorics, 232-241, 1997, Heidelberg: Springer, Heidelberg · doi:10.1007/BFb0045090 |
| [66] | Lin, Y-L; Chwa, K-Y; Ibarra, OH, Fast algorithms for independent domination and efficient domination in trapezoid graphs, Algorithms and Computation, 267-275, 1998, Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-49381-6_29 |
| [67] | Lin, MC; Mizrahi, MJ; Szwarcfiter, JL, Fast algorithms for some dominating induced matching problems, Inf. Process. Lett., 114, 10, 524-528, 2014 · Zbl 1370.05170 · doi:10.1016/j.ipl.2014.04.012 |
| [68] | Lin, MC; Mizrahi, MJ; Szwarcfiter, JL; Pardo, A.; Viola, A., O(n) time algorithms for dominating induced matching problems, LATIN 2014: Theoretical Informatics, 399-408, 2014, Heidelberg: Springer, Heidelberg · Zbl 1405.68143 · doi:10.1007/978-3-642-54423-1_35 |
| [69] | Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Efficient and perfect domination on circular-arc graphs. CoRR arXiv:1502.01523v1 (2015). Electron. Notes Discrete Math. 50, 307-312 (2015) · Zbl 1347.05146 |
| [70] | Livingston, M., Stout, Q.: Distributing resources in hypercube computers. In: Proceedings of Third Conference on Hypercube Concurrent Computers and Applications, pp. 222-231 (1988) |
| [71] | Lokshtanov, D., Pilipczuk, M., van Leeuwen, E.J.: Independence and efficient domination on \(P_6\)-free graphs. CoRR arXiv:1507.02163v2 (2015). Conference Proceedings of SODA 2016, pp. 1784-1803 · Zbl 1409.68145 |
| [72] | Lokshtanov, D., Vatshelle, M., Villanger, Y.: Independent set in \(P_5\)-free graphs in polynomial time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 570-581 (2014) · Zbl 1422.68126 |
| [73] | Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete Math., 2, 253-267, 1972 · Zbl 0239.05111 · doi:10.1016/0012-365X(72)90006-4 |
| [74] | Lu, CL; Ko, M-T; Tang, CY, Perfect edge domination and efficient edge domination in graphs, Discrete Appl. Math., 119, 227-250, 2002 · Zbl 0995.05108 · doi:10.1016/S0166-218X(01)00198-6 |
| [75] | Lu, CL; Tang, CY, Solving the weighted efficient edge domination problem on bipartite permutation graphs, Discrete Appl. Math., 87, 203-211, 1998 · Zbl 0911.05039 · doi:10.1016/S0166-218X(98)00057-2 |
| [76] | Lu, CL; Tang, CY, Weighted efficient domination problem on some perfect graphs, Discrete Appl. Math., 117, 163-182, 2002 · Zbl 0994.05111 · doi:10.1016/S0166-218X(01)00184-6 |
| [77] | Milanič, M.: A hereditary view on efficient domination. In: Proceedings of the 10th Cologne-Twente Workshop. Extended Abstract, pp. 203-206 (2011) |
| [78] | Milanič, M., Hereditary efficiently dominatable graphs, J. Graph Theory, 73, 400-424, 2013 · Zbl 1269.05089 · doi:10.1002/jgt.21685 |
| [79] | Nevries, R.: Efficient domination and polarity. Ph.D. thesis, University of Rostock (2014) |
| [80] | Raychaudhuri, A., On powers of strongly chordal and circular-arc graphs, Ars Combin., 34, 147-160, 1992 · Zbl 0770.05066 |
| [81] | Smart, CB; Slater, PJ, Complexity results for closed neighborhood order parameters, Congr. Numer., 112, 83-96, 1995 · Zbl 0895.05060 |
| [82] | Stockmeyer, LJ; Vazirani, VV, NP-completeness of some generalizations of the maximum matching problem, Inf. Process. Lett., 15, 14-19, 1982 · Zbl 0493.68039 · doi:10.1016/0020-0190(82)90077-1 |
| [83] | Williams, V.V.: Multiplying matrices faster than Coppersmith-Winograd. In: Proceedings of the 44th Symposium on Theory of Computing, STOC 2012, pp. 887-898. ACM, New York (2012) · Zbl 1286.65056 |
| [84] | Yen, C.-C.: Algorithmic aspects of perfect domination. Ph.D. thesis, Institute of Information Science, National Tsing Hua University, Taiwan (1992) |
| [85] | Yen, C-C; Lee, RCT, The weighted perfect domination problem and its variants, Discrete Appl. Math., 66, 147-160, 1996 · Zbl 0848.05042 · doi:10.1016/0166-218X(94)00138-4 |
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.
