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

LIMOS, CNRS UMR 6158, Université Blaise Pascal, Clermont–Ferrand Campus des Cézeaux, 24 avenue des Landais, 63173 Aubière Cedex, France.
christian.laforest@isima.fr.

Received: 13 June 2012
Accepted: 19 March 2013

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.