Let be a directed, arc weighted network with node set V and arc set A. Associated with each arc is a non-negative distance and a non-negative cost or 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 and whose removal from N results in the greatest increase in the shortest distance between two specified nodes s and t in V. The authors show this problem to be NP-hard. In addition, they show that a closely related problem, whose solution provides a lower bound on the optimal solution value of MVAP, is polynomially solvable.
