Constructive–destructive heuristics for the 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. We tackle the problem with various approaches based on randomised constructive and destructive procedures, comparing them with each other and with the only other existing heuristic approach, that is a randomised destructive heuristic. The experiments concern all the available benchmark instances (random graphs up to 60 vertices), but also new benchmark instances with larger size and different topologies, namely random, small-world, regular, planar, grid and real-world graphs up to 300 vertices. Dense random graphs, in fact, appear to become progressively easier to solve as their size grows. On the other instances, the best performance is obtained by combining a randomised constructive procedure, a deterministic destructive procedure, and delayed termination conditions that allow a deeper exploration of the feasible region.