Abstract
We show that the number of minimal dominating sets in a graph on n vertices is at most 1.7697n, thus improving on the trivial \(\mathcal{O}(2^{n}/\sqrt{n})\) bound. Our result makes use of the measure and conquer technique from exact algorithms, and can be easily turned into an \(\mathcal{O}(1.7697^{n})\) listing algorithm.
Based on this result, we derive an \(\mathcal{O}(2.8805^{n})\) algorithm for the domatic number problem, and an \(\mathcal{O}(1.5780^{n})\) algorithm for the minimum-weight dominating set problem. Both algorithms improve over the previous algorithms.
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
Beigel, R.: Finding maximum independent sets in sparse and general graphs. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 856–857. ACM and SIAM (1999)
Brègman, L.M.: Certain properties of nonnegative matrices and their permanents. Doklady Akademii Nauk BSSR 211, 27–30 (1973)
Byskov, M., Eppstein, D.: An algorithm for enumerating maximal bipartite subgraphs (manuscript 2004)
Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Schöning, U.: A deterministic \((2-2/(k+1))\sp n\) algorithm for k-SAT based on local search. Theoretical Computer Science 289, 69–83 (2002)
Edmonds, J., Johnson, E.L.: Matching: A well-solved class of integer linear programs. In: Combinatorial Structures and their Applications, pp. 89–92. Gordon and Breach, New York (1970)
Egorychev, G.P.: Proof of the van der Waerden conjecture for permanents. Sibirsk. Mat. Zh. 22, 65–71, 225 (1981)
Eppstein, D.: Small maximal independent sets and faster exact graph coloring. Journal of Graph Algorithms and Applications 7, 131–140 (2003)
Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proceedings of the 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), pp. 781–790. ACM and SIAM (2004)
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. 191–203. Springer, Heidelberg (2005)
Fomin, F.V., Kratsch, D., Todinca, I.: Exact algorithms for treewidth and minimum fill-in. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 568–580. Springer, Heidelberg (2004)
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)
Grandoni, F.: Exact algorithms for hard graph problems. PhD thesis, Università di Roma “Tor Vergata”, Roma, Italy (March 2004)
Grandoni, F.: A note on the complexity of minimum dominating set. Journal of Discrete Algorithms (to appear)
Haynes, T.W., Hedetniemi, S.T. (eds.): Domination in graphs. Marcel Dekker Inc., New York (1998)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of SIAM 10, 196–210 (1962)
Iwama, J., Tamaki, S.: Improved upper bounds for 3-sat. In: 15th ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), p. 328. ACM and SIAM (2004)
Lawler, E.L.: A note on the complexity of the chromatic number problem. Information Processing Lett. 5, 66–67 (1976)
Moon, J.W., Moser, L.: On cliques in graphs. Israel Journal of Mathematics 3, 23–28 (1965)
Randerath, B., Schiermeyer, I.: Exact algorithms for MINIMUM DOMINATING SET, Technical Report zaik-469, Zentrum für Angewandte Informatik Köln, Germany (2004)
Reige, T., Rothe, J.: An exact 2.9416n algorithm for the three domatic number problem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 733–744. Springer, Heidelberg (2005)
Tarjan, R.E., Trojanowski, A.E.: Finding a maximum independent set. SIAM Journal on Computing 6, 537–546 (1977)
van der Waerden, B.: Problem 45. Jahresber. Deutsch. Math.-Verein. 35, 117 (1926)
Woeginger, G.: 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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fomin, F.V., Grandoni, F., Pyatkin, A.V., Stepanov, A.A. (2005). Bounding the Number of Minimal Dominating Sets: A Measure and Conquer Approach. In: Deng, X., Du, DZ. (eds) Algorithms and Computation. ISAAC 2005. Lecture Notes in Computer Science, vol 3827. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11602613_58
Download citation
DOI: https://doi.org/10.1007/11602613_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-30935-2
Online ISBN: 978-3-540-32426-3
eBook Packages: Computer ScienceComputer Science (R0)