The Weighted Safe Set Problem (WSSP)

This page collects benchmark instances and best known results.

The problem

A connected undirected graph G = (V,E) is given, with a weight function w on the vertices.

Find a subset of vertices S of minimum total weight such that each connected component of the subgraph induced by S exceeds the weight of each connected component of the subgraph induced by V \ S.

Test instances

• Macambira et al. (from 10 to 30 vertices)
• Hosteins (from 20 to 50 vertices)
• Boggio Tomasaz et al. (60 vertices)
• Boggio Tomasaz et al. (dense instances from 100 to 300 vertices)
• Boggio Tomasaz et al. (sparse instances from 100 to 300 vertices)

• A. Boggio Tomasaz, R. Cordone and P. Hosteins, A combinatorial branch-and-bound for the Safe Set Problem. Networks, 81(4):445–464, June 2023 [DOI: 10.1002/net.22140]
• A. Boggio Tomasaz, R. Cordone, and P. Hosteins. Constructive-destructive heuristics for the safe set problem. Computers & Operations Research, 159: 106311, November 2023 [DOI: 10.1016/j.cor.2023.106311]
• A. Boggio Tomasaz, R. Cordone and P. Hosteins, GRASP approaches for the Weighted Safe Set Problem. International Symposium on Combinatorial Optimization (ISCO 2022)
• A. Boggio Tomasaz and R. Cordone, A revisited branch and bound method for the Weighted Safe Set problem. 13th International Conference on Operations Research and Enterprise Systems (ICORES 2024)
• A. Boggio Tomasaz and R. Cordone, A Scatter Search Metaheuristic and Improvements to an Exact Algorithm for the Weighted Safe Set Problem. Communications in Computer and Information Science [invited]

Best known results

• Optimal results, lower and upper bounds (from 10 to 60 vertices)
• Upper bounds (dense and sparse instances from 100 to 300 vertices)
• Lower and upper bounds (dense instances from 50 to 300 vertices)
• Best known upper and lower bounds for sparse instances from 100 to 300 vertices and results of Scatter Search and branch and bound up to 100 vertices

Pagina aggiornata il