A combinatorial branch and bound for the safe set problem. Issue 4 (23rd December 2022)

• Record Type: Journal Article
• Authors: Boggio Tomasaz, Alberto; Cordone, Roberto; Hosteins, Pierre
• Is Part Of: Networks. Volume 81:Issue 4(2023)
• Page Start: 445
• Page End: 464
• Publication Date: 2022-12-23
• Subjects: branch and bound -- graph partitioning -- safe set; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.22140
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: The Weighted Safe Set Problem requires to partition an undirected graph into two families of connected components, respectively denoted as safe and unsafe, in such a way that each safe component dominates the unsafe adjacent components with respect to a weight function. We introduce a combinatorial branch and bound approach, whose main strength is a refined relaxation that combines graph manipulations and the solution of an auxiliary problem. We also propose fixing procedures to reduce the number of branching nodes. The algorithm solves all weighted instances available in the literature and most unweighted ones, up to 50 vertices, with computational times orders of magnitude smaller than the competing algorithms. In order to investigate the limits of the approach, we introduce a benchmark of graphs with 60 vertices, solving to optimality the denser instances.