Matheurísticas para o Problema do Safe Set

Abstract

The Safe Set Problem (SSP) consists in identifying, in a connected graph, a subset of vertices capable of structurally dominating the adjacent components, ensuring that each internal component has weight greater than or equal to that of the external components to which it is connected. It is an NP-hard problem with applications in social networks, stability of vulnerable systems, and the organization of refuges in buildings. Due to its computational complexity, exact methods face limitations for large-scale instances, which motivates the use of approximate strategies. This work proposes a matheuristic composed of two stages: (i) a constructive phase based on a randomized greedy heuristic, responsible for generating feasible initial solutions, and (ii) an optimization phase using the Large Neighbourhood Search (LNS) approach, which partially destroys and reconstructs the solution by relying on the compact Integer Linear Programming model proposed by Hosteins (2020). Experiments were conducted on 120 pseudo-random instances from the literature, varying graph size, density, and vertex selection strategies. The results show that the matheuristic produces good-quality solutions in reduced time, with an average reduction of approximately 50% relative to the value of the initial solutions, and superior performance on larger and denser instances. The strategies with the highest number of constructive iterations (B-10 and F-10) stood out, especially configuration F-10, which achieved the best solutions in most cases. The results confirm the effectiveness of combining greedy heuristics and LNS guided by ILP as a promising alternative for solving the SSP.