Abstract
This paper deals with the Efficient Edge Domination Problem (EED, for short), also known as Dominating Induced Matching Problem. For an undirected graph G = (V,E) EED asks for an induced matching M ⊆ E that simultaneously dominates all edges of G. Thus, the distance between edges of M is at least two and every edge in E is adjacent to an edge of M. EED is related to parallel resource allocation problems, encoding theory and network routing. The problem is \(\mathbb{NP}\)-complete even for restricted classes like planar bipartite and bipartite graphs with maximum degree three. However, the complexity has been open for chordal bipartite graphs.
This paper shows that EED can be solved in polynomial time on hole-free graphs. Moreover, it provides even linear time for chordal bipartite graphs.
Finally, we strengthen the \(\mathbb{NP}\)-completeness result to planar bipartite graphs of maximum degree three.
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., Barkauskas, A., Slater, P.: Efficient near-domination of graphs. Congr. Numer. 58, 83–92 (1987)
Bange, D., Barkauskas, A., Slater, P.: Efficient domination sets in graphs. In: Ringeisen, R.D., Roberts, F.S. (eds.) Applications of Discrete Mathematics, pp. 189–199. SIAM, Philadelphia (1988)
Biggs, N.: Perfect codes in graphs. J. Combin. Theory Ser. B 15, 289–296 (1973)
Bodlaender, H.L.: A tourist guide through treewidth. Acta Cybernetica 11, 1–23 (1993)
Brandstädt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. SIAM Monographs on Discrete Math. Appl., vol. 3. SIAM, Philadelphia (1999)
Cardozo, D.M., Lozin, V.V.: Dominating induced matchings. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds.) Graph Theory, Computational Intelligence and Thought. LNCS, vol. 5420, pp. 77–86. Springer, Heidelberg (2009)
Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs. Academic Press, London (1980)
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)
Laroche, P.: Planar monotone 1-in-3 satisfiability is NP-complete. In: ASMICS Workshop on Tilings, Deuxième Journées Polyominos et pavages, Ecole Normale Supérieure de Lyon (1992)
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)
Livingston, M., Stout, Q.: Distributing resources in hypercube computers. In: Proceedings 3rd Conf. on Hypercube Concurrent Computers and Applications, pp. 222–231 (1988)
Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Applied Math. 119(3), 227–250 (2002)
Lu, C.L., Tang, C.Y.: Efficient domination in bipartite graphs (1997) (manuscript)
Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Applied Math. 87, 203–211 (1998)
Tarjan, R.E.: Depth-First Search and Linear Graph Algorithms. SIAM J. Comput. 1(2), 146–160 (1972)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Brandstädt, A., Hundt, C., Nevries, R. (2010). Efficient Edge Domination on Hole-Free Graphs in Polynomial Time. In: López-Ortiz, A. (eds) LATIN 2010: Theoretical Informatics. LATIN 2010. Lecture Notes in Computer Science, vol 6034. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12200-2_56
Download citation
DOI: https://doi.org/10.1007/978-3-642-12200-2_56
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-12199-9
Online ISBN: 978-3-642-12200-2
eBook Packages: Computer ScienceComputer Science (R0)