Solving 2-Domination Problem in Graphs Using Genetic Algorithm

In a simple, undirected graph G(V, E), a 2-dominating set is a subset R of vertices such that every vertex u in V − R has at least two neighbours in R. The 2-domination number denoted by γ2(G) is the minimum cardinality of a 2-dominating set of G. Given a graph G, determining γ2(G) is termed as 2-domination problem (2-DOM). 2-DOM is known to be NP-hard but there are no known metaheuristic algorithms for solving the problem. In order to counter this, we propose a genetic algorithm-based solution which gives a near optimal solution for 2-DOM problem. The proposed algorithm uses a heuristic to generate a population of feasible solutions and generate a better feasible solution by passing it through various steps of genetic algorithm. Initially, experiments were carried out on graphs for which optimal values are known to verify the algorithm’s effectiveness. The experiments were also carried out on random graphs generated using Erdős-Rényi graph model, a prominent graph model for graph generation and Harwell-Boeing (HB) data set, a well-known data set for graph problems. Since there exists no metaheuristic algorithms for solving the 2-DOM problem, our results set a benchmark for future research on the problem.