Lower and upper bounding strategies for the network disconnection problem

The network disconnection problem is to find a set of edges such that the total cost of removing the edges is no more than a given budget and the weight of nodes disconnected from a designated source by removing edges is maximized. Martel et al. have shown that the problem with unit capacity and unit demand is NP-hard and Myung and Kim present an integer programming formulation and develop an algorithm that includes a preprocessing procedure and lower and upper bounding strategies. In this paper, we present new findings on the properties of the optimal solution and an alternative integer programming formulation, based on which new lower and upper bounding strategies are developed. Computational results for evaluating the performance of the proposed algorithm are also presented.