A new formulation for the Weighted Safe Set Problem

Given a connected graph G = (V, E), a Safe Set S is a subset of the vertex set V such that the cardinality of each connected component in the subgraph induced by V S does not exceed the cardinality of any connected component in the subgraph induced by S, whenever there is an edge in G between vertices of the two components. When the vertices of G are weighted, the weight of a component is defined as the sum of the weights of its vertices, and the notion of safe set is extended by considering the weight of connected components in subgraphs induced by S and by V S. We propose an integer linear formulation for the Weighted Safe Set Problem that uses only one variable per vertex. The formulation has an exponential number of constraints, which can be generated on-the-fly within a branch-and-cut algorithm. We describe a linear-time separation algorithm for these constraints. In addition, we describe families of cuts based on cliques and on minimum weight cut separators, and discuss separation algorithms. A branch-and-cut algorithm that solves the proposed formulation is computationally compared with two alternative formulations from the literature, and shows faster in solving most of benchmark instances with low edge density.