Abstract
Say that an edge of a graph G dominates itself and every other edge sharing a vertex of it. An edge dominating set of a graph G = (V,E) is a subset of edges E′ ⊆ E which dominates all edges of G. In particular, if every edge of G is dominated by exactly one edge of E′ then E′ is a dominating induced matching. It is known that not every graph admits a dominating induced matching, while the problem to decide if it does admit it is NP-complete. In this paper we consider the problems of finding a minimum weighted dominating induced matching, if any, and counting the number of dominating induced matchings of a graph with weighted edges. We describe an exact algorithm for general graphs that runs in O *(1.1939n) time and polynomial (linear) space, for solving these problems. This improves over the existing exact algorithms for the problems in consideration.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bjorklund, A.: Determinant sums for undirected hamiltonicity. In: Annual Symposium on Foundations of Computer Science, FOCS 2010, pp. 173–182 (2010)
Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets möbius: fast subset convolution. In: Annual Symposium on Foundations of Computer Science, STOC 2007, pp. 67–74 (2007)
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., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: Chao, K.-M., Hsu, T.-S., Lee, D.-T. (eds.) ISAAC 2012. LNCS, vol. 7676, pp. 267–277. Springer, Heidelberg (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)
Brandstädt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Combinatoria 67, 273–281 (2003)
Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Applied Mathematics 159, 21–531 (2011)
Cardoso, 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)
Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Applied Mathematics 156, 3060–3065 (2008)
Dahllöf, V., Jonsson, P., Wahlström, M.: Counting models for 2sat and 3sat formulae. Theoretical Computer Science 332, 265–291 (2005)
Dahllöf, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: ACM-SIAM Symposium on Discrete Algorithms, SODA 2002, pp. 292–298 (2002)
Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54, 181–207 (2009)
Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: a simple O *(1.220n) independent set algorithm. In: SODA 2006 ACM-SIAM Symposium on Discrete Algorithms, pp. 18–25 (2006)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. EATCS Series in Theoretical Computer Science. Springer, Berlin (2010)
Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Information Processing Letters 48, 221–228 (1993)
Gupta, S., Raman, V., Saurabh, S.: Maximum r-regular induced subgraph problem: Fast exponential algorithms and combinatorial bounds. SIAM Journal on Discrete Mathematics 26, 1758–1780 (2012)
Korpelainen, N.: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs. Electronic Notes in Discrete Mathematics 32, 133–140 (2009)
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Exact algorithms for dominating induced matchings. CoRR, abs/1301.7602 (2013)
Livingston, M., Stout, Q.F.: Distributing resources in hypercube computers. In: C3P Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, vol. 1, pp. 222–231. ACM (1988)
Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Applied Mathematics 119, 227–250 (2002)
Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Applied Mathematics 87, 203–211 (1998)
Milanic, M.: Hereditary efficiently dominatable graphs. Journal of Graph Theory 73, 400–424 (2013)
van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. In: Fiat, A., Sanders, P. (eds.) ESA 2009. LNCS, vol. 5757, pp. 554–565. Springer, Heidelberg (2009)
Wahlström, M.: A tighter bound for counting max-weight solutions to 2SAT instances. In: Grohe, M., Niedermeier, R. (eds.) IWPEC 2008. LNCS, vol. 5018, pp. 202–213. Springer, Heidelberg (2008)
Woeginger, G.J.: Exact algorithms for NP-hard problems: a survey. In: Combinatorial Optimization - Eureka, you Shrink!, pp. 185–207. Springer-Verlag New York, Inc., New York (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L. (2013). An O *(1.1939n) Time Algorithm for Minimum Weighted Dominating Induced Matching. In: Cai, L., Cheng, SW., Lam, TW. (eds) Algorithms and Computation. ISAAC 2013. Lecture Notes in Computer Science, vol 8283. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-45030-3_52
Download citation
DOI: https://doi.org/10.1007/978-3-642-45030-3_52
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-45029-7
Online ISBN: 978-3-642-45030-3
eBook Packages: Computer ScienceComputer Science (R0)