A new formulation for the Safe Set problem on graphs

摘要

Let G = (V, E) be a finite simple connected graph and S be a non-empty subset of V, the subgraph of G induced by the subset S is denoted by G[S]. Consider the function w, which assigns a positive real number as a weight to each vertex belonging to V and for a subset S of V, let w(S) be the sum of all weights of the vertices belonging to S. A subset S of V is a weighted Safe Set if, for any maximal component C of G[S], w(C) is greater or equal than w(D) for every maximal component D of G[V S] connected to C. A maximal component C of G[S] is a subset of vertices in which all its adjacent vertices do not belong to S. If every vertex belonging to V has a weight equal to one, the non-empty subset S of V is called a Safe Set. Furthermore, if G[S] is connected, it characterizes a Connected Safe Set. The optimal solution of the Safe Set Problem is a subset S which minimizes w(S). This work presents a mixed integer linear programming formulation and a Branch and Cut algorithm for both the Weighted Safe Set and the Safe Set problems. In addition, for the Safe Set problem, a pre-processing test is suggested. This work also contributes with a heuristic procedure for the Weighted Safe Set and the Safe Set problems. Computational experiments showed the efficiency of each of the proposed methods. (C) 2019 Elsevier Ltd. All rights reserved.