Improved local search for the minimum weight dominating set problem in massive graphs by using a deep optimization mechanism

The minimum weight dominating set (MWDS) problem is an important generalization of the minimum dominating set problem with various applications. In this work, we develop an efficient local search scheme that can dynamically adjust the number of added and removed vertices according to the information of the candidate solution. Based on this scheme, we further develop three novel ideas to improve performance, resulting in our so-called DeepOpt-MWDS algorithm. First, we use a new construction method with five reduction rules to significantly reduce massive graphs and construct an initial solution efficiently. Second, an improved configuration checking strategy called CC2V3+ is designed to reduce the cycling phenomenon in local search. Third, a general perturbation framework called deep optimization mechanism (DeepOpt) is proposed to help the algorithm avoid local optima and to converge to a new solution quickly. Extensive experiments based on eight popular benchmarks of different scales are carried out to evaluate the proposed algorithm. Compared to seven state-of-the-art heuristic algorithms, DeepOpt-MWDS performs better on random and classic benchmarks and obtains the best solutions on almost all massive graphs. We investigate three main algorithmic ingredients to understand their impacts on the performance of the proposed algorithm. Moreover, we adapt the proposed general framework DeepOpt to another NP-hard problem to verify its generality and achieve good performance.