A frequency and two-hop configuration checking-driven local search algorithm for the minimum weakly connected dominating set problem

Abstract

The minimum weakly connected dominating set problem is a typical NP-hard problem with a wide range of applications. To solve this problem, we propose a frequency property and two-hop configuration checking strategy-driven local search algorithm (FCC²LS). In this algorithm, we first propose a lock-vertex-based initial solution construction procedure. This procedure guarantees that certain vertices, which must be included in the optimal solution, are added to the solution. Second, we propose a two-hop configuration checking strategy and a frequency property. The two-hop configuration checking strategy is a new variant of the original configuration checking strategy, which prohibits vertices with unchanged configuration from being added to the candidate solution. The frequency property is used to record the number of times for each vertex is added to the solution, which can increase the diversity of selected vertices. Third, we combine two scoring functions, Dscore and Nscore, with the above strategies and propose effective vertex selection methods to help the algorithm select suitable vertices to add into or remove from the candidate solutions. Finally, we evaluate the proposed algorithm FCC²LS with four state-of-the-art algorithms on four groups of benchmark instances. Experimental results show that our algorithm performs better on four classical benchmark instances.