Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic

Christian Laforest; Raksmey Phan

RAIRO - Operations Research - Recherche Opérationnelle (2013)

  • Volume: 47, Issue: 3, page 199-221
  • ISSN: 0399-0559

Abstract

top
In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including cuts in the search process. We then experiment it and show that it is able to solve almost all instances up to 50 vertices in reasonable time and some instances up to several hundreds of vertices. To go further and to treat larger graphs, we analyze a greedy heuristic. We show that it often gives good (sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s. That sort of heuristic is a good approach to get an initial solution for our exact method. We also describe and analyze some of its worst cases.

How to cite

top

Laforest, Christian, and Phan, Raksmey. "Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic." RAIRO - Operations Research - Recherche Opérationnelle 47.3 (2013): 199-221. <http://eudml.org/doc/275047>.

@article{Laforest2013,
abstract = {In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including cuts in the search process. We then experiment it and show that it is able to solve almost all instances up to 50 vertices in reasonable time and some instances up to several hundreds of vertices. To go further and to treat larger graphs, we analyze a greedy heuristic. We show that it often gives good (sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s. That sort of heuristic is a good approach to get an initial solution for our exact method. We also describe and analyze some of its worst cases.},
author = {Laforest, Christian, Phan, Raksmey},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {combinatorial optimization; heuristics; exact algorithm; worst case analysis; experimentations; independent dominating set in graphs},
language = {eng},
number = {3},
pages = {199-221},
publisher = {EDP-Sciences},
title = {Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic},
url = {http://eudml.org/doc/275047},
volume = {47},
year = {2013},
}

TY - JOUR
AU - Laforest, Christian
AU - Phan, Raksmey
TI - Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2013
PB - EDP-Sciences
VL - 47
IS - 3
SP - 199
EP - 221
AB - In this paper we present a new approach to solve the Minimum Independent Dominating Set problem in general graphs which is one of the hardest optimization problem. We propose a method using a clique partition of the graph, partition that can be obtained greedily. We provide conditions under which our method has a better complexity than the complexity of the previously known algorithms. Based on our theoretical method, we design in the second part of this paper an efficient algorithm by including cuts in the search process. We then experiment it and show that it is able to solve almost all instances up to 50 vertices in reasonable time and some instances up to several hundreds of vertices. To go further and to treat larger graphs, we analyze a greedy heuristic. We show that it often gives good (sometimes optimal) results in large instances up to 60   000 vertices in less than 20 s. That sort of heuristic is a good approach to get an initial solution for our exact method. We also describe and analyze some of its worst cases.
LA - eng
KW - combinatorial optimization; heuristics; exact algorithm; worst case analysis; experimentations; independent dominating set in graphs
UR - http://eudml.org/doc/275047
ER -

References

top
  1. [1] L. Baez-Duarte, Hardy–ramanujan’s asymptotic formula for partitions and the central limit theorem. Adv. Math.125 (1997) 114–120. Zbl0873.60010MR1427803
  2. [2] N. Bourgeois, B. Escoffier and V.T. Paschos, Fast algorithm for min independent dominating set. SIROCCO, Lect. Notes Comput. Sci. 6058 (2010) 247–261. Zbl1284.05270MR2671377
  3. [3] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP–Completeness (Series of Books in the Mathematical Sciences). W.H. Freeman and Co Ltd, first edition edition (1979). Zbl0411.68039MR519066
  4. [4] M.M. Halldórsson. Approximating the minimum maximal independence number. Inf. Process. Lett.46 (1993) 169–172. Zbl0778.68041MR1229204
  5. [5] F. Harary and M. Livingston, Independent domination in hypercubes. Appl. Math. Lett.6 (1993) 27–28. Zbl0780.05031MR1347282
  6. [6] J. Haviland, Independent domination in triangle–free graphs. Discrete Math.308 (2008) 3545–3550. Zbl1168.05347MR2421675
  7. [7] D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, On generating all maximal independent sets. Inf. Process. Lett.27 (1988) 119–123. Zbl0654.68086MR933271
  8. [8] F. Kuhn, T. Nieberg, T. Moscibroda and R. Wattenhofer, Local approximation schemes for ad hoc and sensor networks. DIALM-POMC (2005) 97–103. 
  9. [9] J. Little, Branch and Bound Methods for Combinatorial Problems. Ulan Press (2012). 
  10. [10] C. Liu and Y. Song, Exact algorithms for finding the minimum independent dominating set in graphs. ISAAC, Lect. Notes Comput. Sci. 4288 (2006) 439–448. Zbl1135.05315MR2296126
  11. [11] Y.L. Orlovich, V.S. Gordon and D. de Werra, On the inapproximability of independent domination in 2p3–free perfect graphs. Theor. Comput. Sci.410 (2009) 977–982. Zbl1162.68027MR2492039
  12. [12] A. Potluri and A. Negi, Some observations on algorithms for computing minimum independent dominating set. in Springer IC3, Commun. Comput. Inf. Sci. 168 (2011) 57–68. 
  13. [13] W.C. Shiu, X.-G. Chen and W.H. Chan, Triangle–free graphs with large independent domination number. Discrete Optim.7 (2010) 86–92. Zbl1264.05095MR2609062
  14. [14] Y. Song, T. Liu and K. Xu, Independent domination on tree convex bipartite graphs, in Frontiers in Algorithmics and Algorithmic Aspects in Information and Management, edited by J. Snoeyink, P. Lu, K. Su and L. Wang. Springer Berlin Heidelberg, Lect. Notes Comput. Sci. 7285 (2012) 129–138. Zbl1304.68064
  15. [15] J. Steele, The Cauchy–Schwarz master class: an introduction to the art of mathematical inequalities. MAA problem books series. Cambridge University Press (2004). Zbl1060.26023MR2062704

NotesEmbed ?

top

You must be logged in to post comments.