A Revisited Branch and Bound Method for the Weighted Safe Set Problem

The Weighted Safe Set Problem requires to partition an undirected graph into two families of connected components, respectively denoted as safe and unsafe, in such a way that each safe component dominates the unsafe adjacent components with respect to a weight function. We introduce some improvements to an existing exact approach that produce a significant reduction in the effort required to find the optimum or in the gap between the optimum and the best solution obtained within a given time limit. The first improvement consists of a relaxation that is weaker than the original one, but allows to adopt a more effective branching strategy and stronger variable fixing procedures. The second one is the integration of a dedicated heuristic in the exact ap- proach. The experimental results show a strong average reduction of the computational time and the number of branching nodes. This also mitigates the anticipated termination of the algorithm due to the exhaustion of the memory on the largest benchmark instances.