GRASP approaches to the Weighted Safe Set Problem

The Weighted Safe Set Problem aims to determine in an undirected graph a subset of vertices such that the weights of the connected components they induce exceed the weights of the adjacent components induced by the complementary subset. This paper tackles the problem with Greedy Randomized Adaptive Search Procedures based on two different randomisation schemes. Both approaches are tested on new benchmark instances up to 300 vertices, and compared with the only existing heuristic approach (that is a randomised destructive heuristic) on the original benchmark. The results suggest that the use of a restricted candidate list outperforms all the other approaches.