Solving connected dominating set faster than \(2^n\). (English) Zbl 1170.68030
Summary: 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 \(\Omega (2^n)\) algorithm that 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 a 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 \(2 n\) barrier, by presenting a simple \(O(1.9407^n)\) 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.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
Keywords:
exponential-time exact algorithm; NP-hard problem; connected dominating set; maximum leaf spanning treeReferences:
| [1] | Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). J. Algorithms 54, 168–204 (2005) · Zbl 1101.68716 · doi:10.1016/j.jalgor.2004.06.008 |
| [2] | Björklund, A., Husfeldt, T.: Inclusion-exclusion algorithms for counting set partitions. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 575–582. IEEE (2006) · Zbl 1170.68651 |
| [3] | 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) · Zbl 1117.90303 |
| [4] | Brueggemann, T., Kern, W.: An improved deterministic local search algorithm for 3-SAT. Theor. Comput. Sci. 329, 303–313 (2004) · Zbl 1086.68051 · doi:10.1016/j.tcs.2004.08.002 |
| [5] | Byskov, J.M.: Enumerating maximal independent sets with applications to graph colouring. Oper. Res. Lett. 32, 547–556 (2004) · Zbl 1052.05055 · doi:10.1016/j.orl.2004.03.002 |
| [6] | Dantsin, E., Goerdt, A., Hirsch, E.A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., Schöning, U.: A deterministic (2/(k+1)) n algorithm for k-SAT based on local search. Theor. Comput. Sci. 289, 69–83 (2002) · Zbl 1061.68071 · doi:10.1016/S0304-3975(01)00174-8 |
| [7] | Eppstein, D.: The traveling salesman problem for cubic graphs. In: Workshop on Algorithms and Data Structures (WADS), pp. 307–318 (2003) · Zbl 1206.68143 |
| [8] | Eppstein, D.: Quasiconvex analysis of backtracking algorithms. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 781–790 (2004) |
| [9] | Fomin, F.V., Gaspers, S., Pyatkin, A.V.: Finding a minimum feedback vertex set in time O(1.7548 n ). In: Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC 2006). Lecture Notes in Computer Science, vol. 4169, pp. 184–191. Springer, Berlin (2006) · Zbl 1154.05327 |
| [10] | Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and conquer: domination–A case study. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005). Lecture Notes in Computer Science, vol. 3580, pp. 191–203. Springer, Berlin (2005) · Zbl 1082.68866 |
| [11] | Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bull. EATCS 87, 47–77 (2005) · Zbl 1169.68669 |
| [12] | Fomin, F.V., Grandoni, F., Kratsch, D.: Measure and Conquer: A simple O(20.288n ) independent set algorithm. In: Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 18–25 (2006) · Zbl 1192.68960 |
| [13] | Fomin, F.V., Kratsch, D., Todinca, I.: Exact algorithms for treewidth and minimum fill-in. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes in Computer Science, vol. 3142, pp. 568–580. Springer, Berlin (2004) · Zbl 1099.68076 |
| [14] | Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings of the 30th Workshop on Graph Theoretic Concepts in Computer Science (WG 2004). Lecture Notes in Computer Science, vol. 3353, pp. 245–256. Springer, Berlin (2004) · Zbl 1112.68420 |
| [15] | Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, New York (1979) · Zbl 0411.68039 |
| [16] | Grandoni, F.: A note on the complexity of minimum dominating set. J. Discrete Algorithms 4(2), 209–214 (2006) · Zbl 1127.05070 · doi:10.1016/j.jda.2005.03.002 |
| [17] | Guha, S., Khuller, S.: Approximation algorithms for connected dominating sets. Algorithmica 20(4), 374–387 (1998) · Zbl 0895.68106 · doi:10.1007/PL00009201 |
| [18] | 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) · Zbl 1192.90226 |
| [19] | Håstad, J.: Clique is hard to approximate within n 1 . Acta Math. 182(1), 105–142 (1999) · Zbl 0989.68060 · doi:10.1007/BF02392825 |
| [20] | Held, M., Karp, R.M.: A dynamic programming approach to sequencing problems. J. SIAM 10, 196–210 (1962) · Zbl 0106.14103 |
| [21] | Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63, 512–530 (2001) · Zbl 1006.68052 · doi:10.1006/jcss.2001.1774 |
| [22] | Iwama, K.: Worst-case upper bounds for k-SAT. Bull. EATCS 82, 61–71 (2004) · Zbl 1169.68443 |
| [23] | Koivisto, M.: An O(2 n ) algorithm for graph coloring and other partitioning problems via inclusion-exclusion. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 583–590. IEEE (2006) |
| [24] | Mölle, D., Richter, S., Rossmanith, P.: A faster algorithm for the steiner tree problem. In: Proceedings of the 23rd Symposium on Theoretical Aspects of Computer Science (STACS 2006). Lecture Notes in Computer Science, vol. 3884, pp. 561–570. Springer, Berlin (2006) · Zbl 1136.68468 |
| [25] | Randerath, B., Schiermeyer, I.: Exact algorithms for MINIMUM DOMINATING SET. Technical Report, zaik-469, Zentrum für Angewandte Informatik Köln, April (2004) · Zbl 1035.05042 |
| [26] | Razgon, I.: Exact computation of maximum induced forest. In: Proceedings of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006). Lecture Notes in Computer Science, vol. 4059, pp. 160–171. Springer, Berlin (2006) · Zbl 1141.05340 |
| [27] | Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7(3), 425–440 (1986) · Zbl 0637.68080 · doi:10.1016/0196-6774(86)90032-5 |
| [28] | Schöning, U.: Algorithmics in exponential time. In: Proceedings of the 22nd International Symposium on Theoretical Aspects of Computer Science (STACS 2005). Lecture Notes in Computer Science, vol. 3404, pp. 36–43. Springer, Berlin (2005) · Zbl 1118.68500 |
| [29] | Swamy, C., Kumar, A.: Primal-dual algorithms for connected facility location problems. Algorithmica 40(4), 245–269 (2004) · Zbl 1108.90026 · doi:10.1007/s00453-004-1112-3 |
| [30] | Williams, R.: A new algorithm for optimal constraint satisfaction and its implications. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004). Lecture Notes in Computer Science, vol. 3142, pp. 1227–1237. Springer, Berlin (2004) · Zbl 1098.68120 |
| [31] | Woeginger, G.J.: Exact algorithms for NP-hard problems: A survey. In: Combinatorial Optimization–Eureka, You Shrink. Lecture Notes in Computer Science, vol. 2570, pp. 185–207. Springer, Berlin (2003) · Zbl 1024.68529 |
| [32] | Woeginger, G.J.: Space and time complexity of exact algorithms: Some open problems. In: Proceedings of the 1st International Workshop on Parameterized and Exact Computation (IWPEC 2004). Lecture Notes in Computer Science, vol. 3162, pp. 281–290. Springer, Berlin (2004) · Zbl 1104.68520 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
