Double Roman Domination Problem: An iterated local search approach

Abstract

In the last few decades, graph domination problems have attracted the attention of both academics and practitioners. In these problems, a subset of vertices is selected such that every vertex in the graph is either in the subset or adjacent to at least one selected vertex. One of the most extended variants is the Roman Domination Problem (RDP), where vertices are assigned values to ensure coverage under specific protection rules. This research addresses the Double Roman Domination Problem (DROMDP), a more restrictive extension of RDP in which stronger domination conditions are imposed to guarantee coverage even under potential vertex failures. In this paper, an algorithm based on the Iterated Local Search (ILS) framework is proposed, considering the use of two constructive procedures, two local search methods, and two perturbation mechanisms to find high-quality solutions. The results obtained are compared with the state-of-the-art method, based on Ant Colony Optimization, with ILS emerging as the most competitive algorithm for DROMDP. These results are supported by an extensive computational experimentation, including an ablation study of the different components, statistical tests, and a Bayesian analysis on the probability of ILS for being the best algorithm for any instance.