Abstract
In the connected dominating set problem we are given an n-node undirected graph, and we are asked to find a minimum cardinality connected subset S of nodes such that each node not in S is adjacent to some node in S. This problem is also equivalent to finding a spanning tree with maximum number of leaves.
Despite its relevance in applications, the best known exact algorithm for the problem is the trivial Ω(2n) algorithm which enumerates all the subsets of nodes. This is not the case for the general (unconnected) version of the problem, for which much faster algorithms are available. Such difference is not surprising, since connectivity is a global property, and non-local problems are typically much harder to solve exactly.
In this paper we break the 2n barrier, by presenting a simple O(1.9407n) algorithm for the connected dominating set problem. The algorithm makes use of new domination rules, and its analysis is based on the Measure and Conquer technique.
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., Eppstein, D.: 3-coloring in time O(1.3289n). Journal of Algorithms 54, 168–204 (2005)
Blum, J., Ding, M., Thaeler, A., Cheng, X.: Connected dominating set in sensor networks and MANETs. In: Handbook of combinatorial optimization. Supplement, vol. B, pp. 329–369. Springer, New York (2005)
Brueggemann, T., Kern, W.: An improved deterministic local search algorithm for 3-SAT. Theoretical Computer Science 329, 303–313 (2004)
Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Operations Research Letters 32, 547–556 (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)
Eppstein, D.: The traveling salesman problem for cubic graphs. In: Dehne, F., Sack, J.-R., Smid, M. (eds.) WADS 2003. LNCS, vol. 2748, pp. 307–318. Springer, Heidelberg (2003)
Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 781–790 (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., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bulletin of the EATCS 87, 47–77 (2005)
Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and Conquer: A simple O(20.288 n) independent set algorithm. In: Proceedings of the17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 18–25 (2006)
Fomin, F.V., Kratsch, D., Todinca, I.: Exact (Exponential) 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)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freemann (1979)
Grandoni, F.: A note on the complexity of minimum dominating set. Journal of Discrete Algorithms 4(2), 209–214 (2006)
Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998)
Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC 2003), pp. 365–372. ACM, New York (2003)
Håstad, J.: Clique is hard to approximate within n 1 − ε. Acta Math. 182(1), 105–142 (1999)
Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. Journal of SIAM, 196–210 (1962)
Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity. Journal of Computer and System Sciences 63, 512–530 (2001)
Iwama, K.: Worst-case upper bounds for k-SAT. Bulletin of the EATCS 82, 61–71 (2004)
Mölle, D., Richter, S., Rossmanith, P.: A faster algorithm for the steiner tree problem. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 561–570. Springer, Heidelberg (2006)
Randerath, B., Schiermeyer, I.: Exact algorithms for MINIMUM DOMINATING SET. Technical Report, zaik-469, Zentrum für Angewandte Informatik Köln (April 2004)
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)
Robson, J.M.: Algorithms for maximum independent sets. Journal of Algorithms 7(3), 425–440 (1986)
Schöning, U.: Algorithmics in exponential time. In: Diekert, V., Durand, B. (eds.) STACS 2005. LNCS, vol. 3404, pp. 36–43. Springer, Heidelberg (2005)
Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245–269 (2004)
Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: Díaz, J., Karhumäki, J., Lepistö, A., Sannella, D. (eds.) ICALP 2004. LNCS, vol. 3142, pp. 1227–1237. Springer, Heidelberg (2004)
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)
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)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fomin, F.V., Grandoni, F., Kratsch, D. (2006). Solving Connected Dominating Set Faster Than 2n . In: Arun-Kumar, S., Garg, N. (eds) FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science. FSTTCS 2006. Lecture Notes in Computer Science, vol 4337. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11944836_16
Download citation
DOI: https://doi.org/10.1007/11944836_16
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49994-7
Online ISBN: 978-3-540-49995-4
eBook Packages: Computer ScienceComputer Science (R0)