The Complexity of Finding Most Vital Arcs and Nodes

Abstract

Let $G(V,E)$ be a graph (either directed or undirected) with a non-negative length $\ell(e)$ associated with each arc $e$ in $E$. For two specified nodes $s$ and $t$ in $V$, the $k$ most vital arcs (or nodes) are those $k$ arcs (nodes) whose removal maximizes the increase in the length of the shortest path from $s$ to $t$. We prove that finding the $k$ most vital arcs (or nodes) is NP-hard, even when all arcs have unit length. We also correct some errors in an earlier paper by Malik, Mittal and Gupta [ORL 8:223-227, 1989]. (Also cross-referenced as UMIACS-TR-95-96)