Abstract
Let G = (V,E) be a graph. A vertex dominates itself and all its neighbors, i.e., every vertex v ∈ V dominates its closed neighborhood N[v]. A vertex set D in G is an efficient dominating (e.d.) set for G if for every vertex v ∈ V, there is exactly one d ∈ D dominating v. An edge set M ⊆ E is an efficient edge dominating (e.e.d.) set for G if it is an efficient dominating set in the line graph L(G) of G. The ED problem (EED problem, respectively) asks for the existence of an e.d. set (e.e.d. set, respectively) in the given graph.
We give a unified framework for investigating the complexity of these problems on various classes of graphs. In particular, we solve some open problems and give linear time algorithms for ED and EED on dually chordal graphs.
We extend the two problems to hypergraphs and show that ED remains \(\mathbb{NP}\)-complete on α-acyclic hypergraphs, and is solvable in polynomial time on hypertrees, while EED is polynomial on α-acyclic hypergraphs and \(\mathbb{NP}\)-complete on hypertrees.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bange, D.W., Barkauskas, A.E., Slater, P.J.: Efficient dominating sets in graphs. In: Ringeisen, R.D., Roberts, F.S. (eds.) Applications of Discrete Math., pp. 189–199. SIAM, Philadelphia (1988)
Bange, D.W., Barkauskas, A.E., Host, L.H., Slater, P.J.: Generalized domination and efficient domination in graphs. Discrete Math. 159, 1–11 (1996)
Belmonte, R., Vatshelle, M.: Graph Classes with Structured Neighborhoods and Algorithmic Applications. In: Kolman, P., Kratochvíl, J. (eds.) WG 2011. LNCS, vol. 6986, pp. 47–58. Springer, Heidelberg (2011)
Bui-Xuan, B.-M., Telle, J.A., Vatshelle, M.: Boolean width of graphs. Theor. Computer Science 412, 5187–5204 (2011)
Berge, C.: Graphs and Hypergraphs. North-Holland (1973)
Biggs, N.: Perfect codes in graphs. J. of Combinatorial Theory (B) 15, 289–296 (1973)
Brandstädt, A., Chepoi, V.D., Dragan, F.F.: The algorithmic use of hypertree structure and maximum neighbourhood orderings. Discrete Applied Math. 82, 43–77 (1998)
Brandstädt, A., Dragan, F.F., Chepoi, V.D., Voloshin, V.I.: Dually chordal graphs. SIAM J. Discrete Math. 11, 437–455 (1998)
Brandstädt, A., Hundt, C., Nevries, R.: Efficient Edge Domination on Hole-Free Graphs in Polynomial Time. In: López-Ortiz, A. (ed.) LATIN 2010. LNCS, vol. 6034, pp. 650–661. Springer, Heidelberg (2010)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Math. Appl., vol. 3. SIAM, Philadelphia (1999)
Brandstädt, A., Leitert, A., Rautenbach, D.: Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs. Technical report CoRR, arXiv:1207.0953v2, cs.DM (2012)
Brandstädt, A., Mosca, R.: Dominating Induced Matchings for P 7-free Graphs in Linear Time. In: Asano, T., Nakano, S.-i., Okamoto, Y., Watanabe, O. (eds.) ISAAC 2011. LNCS, vol. 7074, pp. 100–109. Springer, Heidelberg (2011)
Broersma, H.J., Kloks, T., Kratsch, D., Müller, H.: Independent sets in asteroidal-triple-free graphs. SIAM J. Discrete Math. 12, 276–287 (1999)
Cameron, K.: Induced matchings. Discrete Applied Math. 24, 97–102 (1989)
Cameron, K.: Induced matchings in intersection graphs. Discrete Mathematics 278, 1–9 (2004)
Cameron, K., Sritharan, R., Tang, Y.: Finding a maximum induced matching in weakly chordal graphs. Discrete Math. 266, 133–142 (2003)
Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Applied Math. 156, 3060–3065 (2008)
Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Math. 159, 521–531 (2011)
Chang, J.-M.: Induced matchings in asteroidal-triple-free graphs. Discrete Applied Math. 132, 67–78 (2003)
Chang, G.J., Pandu Rangan, C., Coorg, S.R.: Weighted independent perfect domination on co-comparability graphs. Discrete Applied Math. 63, 215–222 (1995)
Dragan, F.F., Prisacaru, C.F., Chepoi, V.D.: Location problems in graphs and the Helly property. Discrete Mathematics, Moscow 4, 67–73 (1992) (in Russian); The full version appeared as preprint: Dragan, F.F., Prisacaru, C.F., Chepoi, V.D.: r-Domination and p-center problems on graphs: special solution methods and graphs for which this method is usable, Kishinev State University, preprint MoldNIINTI, N. 948–M88 (1987) (in Russian)
Fagin, R.: Degrees of Acyclicity for Hypergraphs and Relational Database Schemes. Journal ACM 30, 514–550 (1983)
Frank, A.: Some polynomial algorithms for certain graphs and hypergraphs. In: Proceedings of the 5th British Combinatorial Conf. (Aberdeen 1975). Congressus Numerantium, vol. XV, pp. 211–226 (1976)
Garey, M.R., Johnson, D.S.: Computers and Intractability – A Guide to the Theory of NP-completeness. Freeman, San Francisco (1979)
Gavril, F.: Maximum weight independent sets and cliques in intersection graphs of filaments. Information Processing Letters 73, 181–188 (2000)
Golumbic, M.C., Lewenstein, M.: New results on induced matchings. Discrete Applied Math. 101, 157–165 (2000)
Grinstead, D.L., Slater, P.L., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Information Processing Letters 48, 221–228 (1993)
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)
Keil, J.M.: The dominating set problem in interval bigraphs, abstract. In: Proceedings of the 3rd Annual Workshop on Algorithmic Graph Theory, Nipissing University, North Bay, Ontario (2012)
Leitert, A.: Das Dominating Induced Matching Problem für azyklische Hypergraphenl. Diploma Thesis, University of Rostock, Germany (2012)
Liang, Y.D., Lu, C.L., Tang, C.Y.: Efficient Domination on Permutation Graphs and Trapezoid Graphs. In: Jiang, T., Lee, D.T. (eds.) COCOON 1997. LNCS, vol. 1276, pp. 232–241. Springer, Heidelberg (1997)
Lin, Y.-L.: Fast Algorithms for Independent Domination and Efficient Domination in Trapezoid Graphs. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol. 1533, pp. 267–275. Springer, Heidelberg (1998)
Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Applied Math. 119, 227–250 (2002)
Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Applied Math. 87, 203–211 (1998)
Lu, C.L., Tang, C.Y.: Weighted efficient domination problem on some perfect graphs. Discrete Applied Math. 117, 163–182 (2002)
Milanič, M.: A hereditary view on efficient domination, extended abstract. In: Proceedings of the 10th Cologne-Twente Workshop, pp. 203–206 (2011); Full version to appear under the title “Hereditary efficiently dominatable graphs”
Yen, C.-C.: Algorithmic aspects of perfect domination. Ph.D. Thesis, Institute of Information Science, National Tsing Hua University, Taiwan (1992)
Yen, C.-C., Lee, R.C.T.: The weighted perfect domination problem and its variants. Discrete Applied Math. 66, 147–160 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brandstädt, A., Leitert, A., Rautenbach, D. (2012). Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs. In: Chao, KM., Hsu, Ts., Lee, DT. (eds) Algorithms and Computation. ISAAC 2012. Lecture Notes in Computer Science, vol 7676. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-35261-4_30
Download citation
DOI: https://doi.org/10.1007/978-3-642-35261-4_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-35260-7
Online ISBN: 978-3-642-35261-4
eBook Packages: Computer ScienceComputer Science (R0)