[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

Exact Algorithms for Minimum Weighted Dominating Induced Matching

  • Published:
Algorithmica Aims and scope Submit manuscript

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' \subseteq 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 counting the number of dominating induced matchings and finding a minimum weighted dominating induced matching, if any, of a graph with weighted edges. We describe three exact algorithms for general graphs. The first runs in linear time for a given vertex dominating set of fixed size of the graph. The second runs in polynomial time if the graph admits a polynomial number of maximal independent sets. The third one is an \(O^*(1.1939^n)\) time and polynomial (linear) space, which improves over the existing algorithms for exactly solving this problem in general graphs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

References

  1. Björklund, A.: Determinant sums for undirected hamiltonicity. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 173–182 (Washington, DC, USA), FOCS ’10, IEEE Computer Society (2010)

  2. Björklund, A., Husfeldt, T.: Exact graph coloring using inclusion-exclusion. In: Kao, M.-Y. (ed.) Encyclopedia of Algorithms. Springer, Berlin (2008)

    Google Scholar 

  3. Björklund, A., Husfeldt, T., Kaski, P., Koivisto, M.: Fourier meets mobius: fast subset convolution. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing (New York, NY, USA), STOC ’07, ACM, pp. 67–74 (2007)

  4. Blank, M.: An estimate of the external stability of a graph without pendant vertices. Prikl. Math. Programmirovanie 10, 3–11 (1973)

    Google Scholar 

  5. Brandstädt, A., Hundt, C., Nevries, R.: Efficient edge domination on hole-free graphs in polynomial time. In: Proceedings of the 9th Latin American Conference on Theoretical Informatics, pp. 650–661 (Berlin, Heidelberg), LATIN’10, Springer (2010)

  6. Brandstädt, A., Leitert, A., Rautenbach, D.: Efficient dominating and edge dominating sets for graphs and hypergraphs. In: (Chao, K.-M., Hsu, T., Lee, D.-T. (eds.) ISAAC, Lecture Notes in Computer Science, vol. 7676, pp. 267–277. Springer (2012)

  7. Brandstädt, A., Lozin, V.V.: On the linear structure and clique-width of bipartite permutation graphs. Ars Comb. 67, 273–281 (2003)

    MathSciNet  MATH  Google Scholar 

  8. 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, Lecture Notes in Computer Science, vol. 7074, pp. 100–109. Springer (2011)

  9. Cardoso, D.M., Korpelainen, N., Lozin, V.V.: On the complexity of the dominating induced matching problem in hereditary classes of graphs. Discrete Appl. Math. 159(7), 521–531 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  10. Cardoso, D.M., Cerdeira, J.O., Delorme, C., Silva, P.C.: Efficient edge domination in regular graphs. Discrete Appl. Math. 156(15), 3060–3065 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  11. 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 , Lecture Notes in Computer Science, vol. 5420, pp. 77–86. Springer (2009)

  12. Cygan, M., Pilipczuk, M.: Even faster exact bandwidth. ACM Trans. Algorithms 8(1), 8 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  13. Dahllöf, V., Jonsson, P.: An algorithm for counting maximum weighted independent sets and its applications. In: Eppstein, D. (ed.) SODA, pp. 292–298. ACM/SIAM, Philadelphia (2002)

    Google Scholar 

  14. Dahllöf, V., Jonsson, P., Wahlström, M.: Counting models for 2SAT and 3SAT formulae. Theor. Comput. Sci. 332(1–3), 265–291 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  15. Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54(2), 181–207 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, Berlin (2010)

    Book  MATH  Google Scholar 

  17. Grinstead, D.L., Slater, P.J., Sherwani, N.A., Holmes, N.D.: Efficient edge domination problems in graphs. Inf. Process. Lett. 48(5), 221–228 (1993)

    Article  MathSciNet  MATH  Google Scholar 

  18. Gupta, S., Raman, V., Saurabh, S.: Maximum r-regular induced subgraph problem: fast exponential algorithms and combinatorial bounds. SIAM J. Discrete Math. 26(4), 1758–1780 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  19. Iwata, Y.: A faster algorithm for dominating set analyzed by the potential method. In: Marx, D., Rossmanith, P. (eds.) Parameterized and Exact Computation—6th International Symposium, IPEC 2011, Saarbrücken, Germany, September 6–8, 2011. Revised Selected Papers, Lecture Notes in Computer Science, vol. 7112, pp. 41–54. Springer (2011)

  20. Korpelainen, N.: A polynomial-time algorithm for the dominating induced matching problem in the class of convex graphs. Electron. Notes Discrete Math. 32, 133–140 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  21. Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: Exact algorithms for dominating induced matchings. CoRR abs/1301.7602 (2013)

  22. Lin, M.C., Mizrahi, M.J., Szwarcfiter, J.L.: An O*(1.1939 n) time algorithm for minimum weighted dominating induced matching. In: Cai, L., Cheng, S.-W., Lam, T.W. (eds.) ISAAC, Lecture Notes in Computer Science, vol. 8283, pp. 558–567. Springer (2013)

  23. Livingston, M., Stout, Q.F.: Distributing resources in hypercube computers. In: Proceedings of the Third Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, vol. 1, pp. 222–231 (New York, NY, USA), C3P, ACM (1988)

  24. Lu, C.L., Ko, M.-T., Tang, C.Y.: Perfect edge domination and efficient edge domination in graphs. Discrete Appl. Math. 119(3), 227–250 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  25. Lu, C.L., Tang, C.Y.: Solving the weighted efficient edge domination problem on bipartite permutation graphs. Discrete Appl. Math. 87(1–3), 203–211 (1998)

    MathSciNet  MATH  Google Scholar 

  26. Milanic, M.: Hereditary efficiently dominatable graphs. J. Graph Theory 73(4), 400–424 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  27. Ore, O.: Theory of graphs. Am. Math. Soc. Colloq. Publ. 38 (1962)

  28. Reed, B.A.: Paths, stars and the number three. Comb. Probab. Comput. 5, 277–295 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  29. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6(3), 505–517 (1977)

    Article  MathSciNet  MATH  Google Scholar 

  30. van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer. In: Fiat, A., Sanders, P. (eds.) ESA, Lecture Notes in Computer Science, vol. 5757, pp. 554–565. Springer (2009)

  31. Wahlström, M.: A tighter bound for counting max-weight solutions to 2sat instances. In: Proceedings of the 3rd International Conference on Parameterized and Exact Computation, pp. 202–213 (Berlin, Heidelberg). IWPEC’08, Springer (2008)

  32. Gerhard, J.: Woeginger, Combinatorial optimization–Eureka, You Shrink!. Springer-Verlag New York Inc., New York (2003)

    Google Scholar 

  33. Xiao, M., Nagamochi, H.: Exact algorithms for dominating induced matching based on graph partition. Discrete Appl. Math. 190–191, 147–162 (2015)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CONICET, Instituto de Cálculo, Buenos Aires, Argentina

    Min Chih Lin & Michel J. Mizrahi

  2. Departamento de Computación, Universidad de Buenos Aires, Buenos Aires, Argentina

    Min Chih Lin & Michel J. Mizrahi

  3. I. Mat., COPPE and NCE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brazil

    Jayme L. Szwarcfiter

  4. Instituto Nacional de Metrologia, Qualidade e Tecnologia, Rio de Janeiro, Brazil

    Jayme L. Szwarcfiter

Authors
  1. Min Chih Lin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michel J. Mizrahi
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jayme L. Szwarcfiter
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Michel J. Mizrahi.

Additional information

M.C. Lin was partially supported by UBACyT Grant 20020120100058, and PICT ANPCyT Grants 2010-1970 and 2013-2205. M.J. Mizrahi was partially supported by PICT ANPCyT Grants 2010-1970 and 2013-2205. J.L. Szwarcfiter was partially supported by CNPq, CAPES and FAPERJ, research agencies.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lin, M.C., Mizrahi, M.J. & Szwarcfiter, J.L. Exact Algorithms for Minimum Weighted Dominating Induced Matching. Algorithmica 77, 642–660 (2017). https://doi.org/10.1007/s00453-015-0095-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-015-0095-6

Keywords

Search

Navigation