Determining the single most vital arc in the maximum flow problem

The most vital arc in the maximum flow problem is that arc whose removal results in the greatest reduction in the value of the maximal flow between a source node and a sink node. This paper develops an algorithm to determine such a most vital arc in the maximum flow problem. We first define the transformed network corresponding to a given network in order to compute the minimal capacity for each candidate arc. The set of candidate arcs for single most vital arc consists of the arcs whose flow is at least as great as the flow over every arc in a minimal cut. As a result, we present a method in which the most vital arc is determined more easily by computing the minimal capacity in the transformed network. The proposed method is demonstrated by numerical example and computational experiment.