Finding the Most Vital Arcs in a Network

Let N = (V, A) be a directed, arc weighted network with node set V and arc set A. Associated with each arc e e A is a non-negative distance d(e) and a non-negative cost c(e) of removing it from N. Let B be the total amount available to spend on removing arcs. The most vital arcs problem (MVAP) is the problem of finding a subset K of arcs such that SeeKc(e) B and whose removal from N results in the greatest increase in the shortest distance between two specified nodes s and t in V. We show this problem to be NP-hard. In addition, we show that a closely related problem, whose solution provides a lower bound on the optimal solution value of MVAP, is polynomially solvable.