Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

An Exact Algorithm for the Minimum Dominating Clique Problem

  • Conference paper
Parameterized and Exact Computation (IWPEC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4169))

Included in the following conference series:

  • 814 Accesses

Abstract

A subset of vertices D ⊆ V of a graph G = (V,E) is a dominating clique if D is a dominating set and a clique of G. The existence problem ‘Given a graph G, is there a dominating clique in G?’ is NP-complete, and thus both the Minimum and the Maximum Dominating Clique problem are NP-hard. We present an O(1.3390n) time algorithm that for an input graph on n vertices either computes a minimum dominating clique or reports that the graph has no dominating clique. The algorithm uses the Branch & Reduce paradigm and its time analysis is based on the Measure & Conquer approach. We also establish a lower bound of Ω(1.2599n) for the worst case running time of our algorithm.

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

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Cozzens, M.B., Kelleher, L.L.: Dominating cliques in graphs. Discrete Math. 86, 101–116 (1990)

    Article  MathSciNet  Google Scholar 

  2. Culberson, J., Gao, Y., Anton, C.: Phase Transitions of Dominating Clique Problem and Their Implications to Satisfiability Search. In: Proc. IJCAI 2005, pp. 78–83 (2005)

    Google Scholar 

  3. Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: Domination – A case study. In: Caires, L., Italiano, G.F., Monteiro, L., Palamidessi, C., Yung, M. (eds.) ICALP 2005. LNCS, vol. 3580, pp. 192–203. Springer, Heidelberg (2005)

    Google Scholar 

  4. Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bull. EATCS 87, 47–77 (2005)

    MATH  MathSciNet  Google Scholar 

  5. Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (Exponential) algorithms for the dominating set problem. In: Hromkovič, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol. 3353, pp. 245–256. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

  6. Garey, M.R., Johnson, D.S.: Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman and Co., San Francisco (1979)

    MATH  Google Scholar 

  7. Gaspers, S., Liedloff, M.: A Branch-and-Reduce Algorithm for Finding a Minimum Independent Dominating Set in Graphs. In: Fomin, F.V. (ed.) WG 2006. LNCS, vol. 4271, pp. 78–89. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  8. Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms 4, 209–214 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  9. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Fundamentals of domination in graphs. Marcel Dekker Inc., New York (1998)

    MATH  Google Scholar 

  10. Haynes, T.W., Hedetniemi, S.T., Slater, P.J.: Domination in graphs: Advanced Topics. Marcel Dekker Inc., New York (1998)

    MATH  Google Scholar 

  11. Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of SIAM, 196–210 (1962)

    Google Scholar 

  12. Iwama, K.: Worst-case upper bounds for ksat. Bull. EATCS 82, 61–71 (2004)

    MATH  MathSciNet  Google Scholar 

  13. Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119–123 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  14. Kratsch, D.: Algorithms. In: Haynes, T., Hedetniemi, S., Slater, P. (eds.) Domination in Graphs: Advanced Topics, pp. 191–231. Marcel Dekker, New York (1998)

    Google Scholar 

  15. Lawler, E.L.: A note on the complexity of the chromatic number problem. Inform. Process. Lett. 5(3), 66–67 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  16. Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23–28 (1965)

    Article  MATH  MathSciNet  Google Scholar 

  17. Randerath, B., Schiermeyer, I.: Exact algorithms for Minimum Dominating Set, Technical Report zaik-469, Zentrum fur Angewandte Informatik, Köln, Germany (April 2004)

    Google Scholar 

  18. Razgon, I.: Exact Computation of Maximum Induced Forest. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 160–171. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  19. Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425–440 (1986)

    Article  MATH  MathSciNet  Google Scholar 

  20. Schöning, U.: Algorithmics in Exponential Time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 36–43. Springer, Heidelberg (2005)

    Chapter  Google Scholar 

  21. Tarjan, R., Trojanowski, A.: Finding a maximum independent set. SIAM J. Comput. 6(3), 537–546 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  22. Villanger, Y.: Improved exponential-time algorithms for treewidth and minimum fill-in. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 800–811. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  23. Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Jünger, M., Reinelt, G., Rinaldi, G. (eds.) Combinatorial Optimization - Eureka, You Shrink! LNCS, vol. 2570, pp. 185–207. Springer, Heidelberg (2003)

    Chapter  Google Scholar 

  24. Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems. In: Downey, R.G., Fellows, M.R., Dehne, F. (eds.) IWPEC 2004. LNCS, vol. 3162, pp. 281–290. Springer, Heidelberg (2004)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. LITA, Université Paul Verlaine – Metz, 57045 Cedex 01, Metz, France

    Dieter Kratsch & Mathieu Liedloff

Authors
  1. Dieter Kratsch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Mathieu Liedloff
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Department of Information and Computing Sciences, Utrecht University, The Netherlands

    Hans L. Bodlaender

  2. University of Tennessee, 37996-3450, Knoxville, Tennessee, U.S.A.

    Michael A. Langston

Rights and permissions

Reprints and permissions

Copyright information

© 2006 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Kratsch, D., Liedloff, M. (2006). An Exact Algorithm for the Minimum Dominating Clique Problem. In: Bodlaender, H.L., Langston, M.A. (eds) Parameterized and Exact Computation. IWPEC 2006. Lecture Notes in Computer Science, vol 4169. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11847250_12

Download citation

  • DOI: https://doi.org/10.1007/11847250_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-39098-5

  • Online ISBN: 978-3-540-39101-2

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation