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

Test set employed in 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 [accepted] [DOI: 10.1016/j.cor.2023.106311] and A. Boggio Tomasaz, R. Cordone and P. Hosteins, GRASP approaches for the Weighted Safe Set Problem. International Symposium on Combinatorial Optimization (ISCO 2022).

• 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)

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)

Pagina aggiornata il