# 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

## Access Full Article

top## Abstract

top## How to cite

topLaforest, 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] L. Baez-Duarte, Hardy–ramanujan’s asymptotic formula for partitions and the central limit theorem. Adv. Math.125 (1997) 114–120. Zbl0873.60010MR1427803
- [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] 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] M.M. Halldórsson. Approximating the minimum maximal independence number. Inf. Process. Lett.46 (1993) 169–172. Zbl0778.68041MR1229204
- [5] F. Harary and M. Livingston, Independent domination in hypercubes. Appl. Math. Lett.6 (1993) 27–28. Zbl0780.05031MR1347282
- [6] J. Haviland, Independent domination in triangle–free graphs. Discrete Math.308 (2008) 3545–3550. Zbl1168.05347MR2421675
- [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] 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. Zbl1135.05315MR2296126
- [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] 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. Zbl1264.05095MR2609062
- [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] 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 ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.