Abstract
An edge dominating set in a graph G=(V,E) is a subset of the edges D⊆E such that every edge in E is adjacent or equal to some edge in D. The problem of finding an edge dominating set of minimum cardinality is NP-hard. We present a faster exact exponential time algorithm for this problem. Our algorithm uses O(1.3226n) time and polynomial space. The algorithm combines an enumeration approach of minimal vertex covers in the input graph with the branch and reduce paradigm. Its time bound is obtained using the measure and conquer technique. The algorithm is obtained by starting with a slower algorithm which is refined stepwisely. In each of these refinement steps, the worst cases in the measure and conquer analysis of the current algorithm are reconsidered and a new branching strategy is proposed on one of these worst cases. In this way a series of algorithms appears, each one slightly faster than the previous one, ending in the O(1.3226n) time algorithm. For each algorithm in the series, we also give a lower bound on its running time.
We also show that the related problems: minimum weight edge dominating set, minimum maximal matching and minimum weight maximal matching can be solved in O(1.3226n) time and polynomial space using modifications of the algorithm for edge dominating set. In addition, we consider the matrix dominating set problem which we solve in O(1.3226n+m) time and polynomial space for n×m matrices, and the parametrised minimum weight maximal matching problem for which we obtain an O ∗(2.4179k) time and space algorithm.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Alber, J., Bodlaender, H.L., Fernau, H., Kloks, T., Niedermeier, R.: Fixed parameter algorithms for dominating set and related problems on planar graphs. Algorithmica 33, 461–493 (2002)
Bodlaender, H.L.: Treewidth algorithmic techniques and results. In: Proceedings of the 22nd International Symposium on Mathematical Foundations of Computer Science, MFCS 1997. Lecture Notes in Computer Science, vol. 1295, pp. 19–36. Springer, Berlin (1997)
Carr, R., Fujito, T., Konjevod, G., Parekh, O.: A 2 1/10-approximation algorithm for a generalization of the weighted edge-dominating set problem. J. Comb. Optim. 5, 317–326 (2001)
Downey, R.G., Fellows, M.R.: Fixed-parameter tractability and completeness. Congr. Numer. 87, 161–178 (1992)
Edmonds, J.: Paths, trees, and flowers. Can. J. Math. 17, 445–467 (1965)
Eppstein, D.: Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. ACM Trans. Algorithms 2, 492–509 (2006)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45, 634–652 (1998)
Fernau, H.: Edge dominating set: efficient enumeration-based exact algorithms. In: Proceedings 2nd International Workshop on Parameterized and Exact Computation, IWPEC 2006. Lecture Notes in Computer Science, vol. 4169, pp. 140–151. Springer, Berlin (2006)
Fomin, F.V., Kratsch, D., Woeginger, G.J.: Exact (exponential) algorithms for the dominating set problem. In: Proceedings 30th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2004. Lecture Notes in Computer Science, vol. 3353, pp. 245–256. Springer, Berlin (2004)
Fomin, F.V., Grandoni, F., Kratsch, D.: Some new techniques in design and analysis of exact (exponential) algorithms. Bull. Eur. Assoc. Theor. Comput. Sci. 87, 47–77 (2005)
Fomin, F.V., Todinca, I., Kratsch, D., Villanger, Y.: Exact algorithms for treewidth and minimum fill-in. SIAM J. Comput. 38, 1058–1079 (2008)
Fomin, F.V., Gaspers, S., Saurabh, S., Stepanov, A.A.: On two techniques of combining branching and treewidth. Algorithmica 54, 181–207 (2009)
Fomin, F.V., Grandoni, F., Kratsch, D.: A measure & conquer approach for the analysis of exact algorithms. J. ACM 56 (2009)
Harary, F.: Graph Theory. Addison-Wesley, Reading (1969)
Held, M., Karp, R.: A dynamic programming approach to sequencing problems. J. SIAM 10, 196–210 (1962)
Iwama, K.: Worst-case upper bounds for ksat. Bull. Eur. Assoc. Theor. Comput. Sci. 82, 61–71 (2004)
Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27, 119–123 (1988)
Kloks, T.: Treewidth. Computations and Approximations. Lecture Notes in Computer Science, vol. 842. Springer, Berlin (1994)
Kullmann, O.: New methods for 3-SAT decision and worst-case analysis. Theor. Comput. Sci. 223(1–2), 1–72 (1999)
Lawler, E.L.: A note on the complexity of the chromatic number problem. Inf. Process. Lett. 5, 66–67 (1976)
Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9, 558–565 (1980)
Moon, J.W., Moser, L.: On cliques in graphs. Isr. J. Math. 3, 23–28 (1965)
Plesník, J.: Equivalence between the minimum covering problem and the maximum matching problem. Discrete Math. 49, 315–317 (1984)
Plesník, J.: Constrained weighted matchings and edge coverings in graphs. Discrete Appl. Math. 92, 229–241 (1999)
Raman, V., Saurabh, S., Sikdar, S.: Efficient exact algorithms through enumerating maximal independent sets and other techniques. Theory Comput. Syst. 42, 563–587 (2007)
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)
Robson, J.M.: Algorithms for maximum independent sets. J. Algorithms 7, 425–440 (1986)
Schiermeyer, I.: Efficiency in exponential time for domination-type problems. Discrete Appl. Math. 156, 3291–3297 (2008)
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)
Tarjan, R.E., Trojanowski, A.: Finding a maximum independent set. SIAM J. Comput. 6, 537–546 (1977)
Telle, J.A., Proskurowski, A.: Algorithms for vertex partitioning problems on partial k-trees. SIAM J. Discrete Math. 10, 529–550 (1997)
van Rooij, J.M.M.: Exact exponential-time algorithms for domination problems in graphs. Ph.D. thesis, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands (2011)
van Rooij, J.M.M., Bodlaender, H.L.: Design by measure and conquer: a faster exact algorithm for dominating set. In: Proceedings of the 25st Symposium on Theoretical Aspects of Computer Science, STACS 2008, pp. 657–668 (2008)
van Rooij, J.M.M., Nederlof, J., van Dijk, T.C.: Inclusion/exclusion meets measure and conquer: exact algorithms for counting dominating sets. In: Proceedings of the 17th Annual European Symposium on Algorithms, ESA 2009. Advanced Research in Computing and Software Science, Lecture Notes in Computer Science, vol. 5757, pp. 554–565. Springer, Berlin (2009)
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)
Woeginger, G.J.: Space and time complexity of exact algorithms: some open problems. In: Proceedings 1st International Workshop on Parameterized and Exact Computation, IWPEC 2004. Lecture Notes in Computer Science, vol. 3162, pp. 281–290. Springer, Berlin (2004)
Yannakakis, M., Gavril, F.: Edge dominating sets in graphs. SIAM J. Appl. Math. 38, 364–372 (1980)
Author information
Authors and Affiliations
Corresponding author
Additional information
This research was partially supported by project BRICKS (Basic Research for Creating the Knowledge Society).
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
van Rooij, J.M.M., Bodlaender, H.L. Exact Algorithms for Edge Domination. Algorithmica 64, 535–563 (2012). https://doi.org/10.1007/s00453-011-9546-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-011-9546-x