Valid inequalities for the $$\beta $$ -edge disruptor problem

The $$\beta $$ -edge disruptor problem ( $$\beta $$ -EDP) aims to identify the minimum weight of edges in an undirected graph, whose removal results in a specific degradation of graph connectivity. This problem is crucial for assessing network vulnerability against disruptive events, providing valuable insights for network security and risk management. Due to its NP-hard nature, solving the problem to optimality is highly challenging. In this paper, we shall provide an efficient algorithm for precisely solving the integer programming (IP) model for the $$\beta $$ -EDP. Firstly, the mixing technique is adapted to derive a family of mixing inequalities for the IP model. Secondly, we introduce the definition of “cover” within the context of the $$\beta $$ -EDP, and propose a family of cover inequalities. We also apply the sequential lifting technique to strengthen the cover inequalities. Moreover, the separation problems associated with both families of inequalities are investigated, with efficient separation procedures developed. Finally, we present specialized cutting plane approaches based on the proposed inequalities. The computational results showcase the effectiveness of integrating our proposed inequalities within an IP solver.