Genetic algorithm based approach for solving Roman {3}-domination problem

Different Roman domination variants have been proposed by researchers to provide better defense strategies under different constraints. A Roman {3}-Dominating Function (RTDF) h on an undirected, simple graph G is a mapping h : V (G) →{0,1,2,3} with two conditions that $\sum\nolimits_{v \in N(u)} h (v) \geq 3$, if h(u) = 0, and $\sum\nolimits_{v \in N(u)} h (v) \geq 2$, if h(u) = 1, where N(u) is the neighbors of vertex u in G. The weight of a RTDF h is the sum $h(V) = \sum\nolimits_{v \in V} h (v)$. Given a graph G, the problem of determining minimum weight of a RTDF of G (also known as Roman {3}-domination number) is known as the Roman {3}-domination problem (MRTDP) and is known to be NP-hard. However no efficient approximation algorithm has been proposed to solve MRTDP. Hence in this paper, we propose a genetic algorithm based approach for solving MRTDP in which four heuristic algorithms have been proposed and a problem specific crossover operator and feasibility function has been developed. Effectiveness of the proposed meta-heuristic algorithm is tested on the random graphs generated using NetworkX Erdős-Rényi model, a popular model for graph generation. Experimental results show that the proposed genetic algorithm for solving MRTDP gives a near optimal solution in reasonable time.