Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 3, pp. 199-221.

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.

DOI : 10.1051/ro/2013034
Classification : 05C69, 05C85
Mots-clés : combinatorial optimization, heuristics, exact algorithm, worst case analysis, experimentations, independent dominating set in graphs 
@article{RO_2013__47_3_199_0,
     author = {Laforest, Christian and Phan, Raksmey},
     title = {Solving the {Minimum} {Independent} {Domination} {Set} {Problem} in {Graphs} by {Exact} {Algorithm} and {Greedy} {Heuristic}},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {199--221},
     publisher = {EDP-Sciences},
     volume = {47},
     number = {3},
     year = {2013},
     doi = {10.1051/ro/2013034},
     mrnumber = {3143749},
     zbl = {1282.05180},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2013034/}
}
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
SP  - 199
EP  - 221
VL  - 47
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2013034/
DO  - 10.1051/ro/2013034
LA  - en
ID  - RO_2013__47_3_199_0
ER  - 
%0 Journal Article
%A Laforest, Christian
%A Phan, Raksmey
%T Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2013
%P 199-221
%V 47
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2013034/
%R 10.1051/ro/2013034
%G en
%F RO_2013__47_3_199_0
Laforest, Christian; Phan, Raksmey. Solving the Minimum Independent Domination Set Problem in Graphs by Exact Algorithm and Greedy Heuristic. RAIRO - Operations Research - Recherche Opérationnelle, Tome 47 (2013) no. 3, pp. 199-221. doi : 10.1051/ro/2013034. http://www.numdam.org/articles/10.1051/ro/2013034/

[1] L. Baez-Duarte, Hardy-ramanujan's asymptotic formula for partitions and the central limit theorem. Adv. Math. 125 (1997) 114-120. | MR | Zbl

[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. | MR | Zbl

[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). | MR | Zbl

[4] M.M. Halldórsson. Approximating the minimum maximal independence number. Inf. Process. Lett. 46 (1993) 169-172. | MR | Zbl

[5] F. Harary and M. Livingston, Independent domination in hypercubes. Appl. Math. Lett. 6 (1993) 27-28. | MR | Zbl

[6] J. Haviland, Independent domination in triangle-free graphs. Discrete Math. 308 (2008) 3545-3550. | MR | Zbl

[7] D.S. Johnson, C.H. Papadimitriou and M. Yannakakis, On generating all maximal independent sets. Inf. Process. Lett. 27 (1988) 119-123. | MR | Zbl

[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] J. Little, Branch and Bound Methods for Combinatorial Problems. Ulan Press (2012).

[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. | MR | Zbl

[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. | MR | Zbl

[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] W.C. Shiu, X.-G. Chen and W.H. Chan, Triangle-free graphs with large independent domination number. Discrete Optim. 7 (2010) 86-92. | MR | Zbl

[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. | Zbl

[15] J. Steele, The Cauchy-Schwarz master class: an introduction to the art of mathematical inequalities. MAA problem books series. Cambridge University Press (2004). | MR | Zbl

Cité par Sources :