In this paper, we consider two problems related to single-commodity flows on a directed network. In the first problem, for a given s – t flow, if an arc is destroyed, all the flow that is passing through that arc is destroyed. What is left flowing from s to t is the residual flow. The objective is to determine a flow pattern such that the residual flow is maximized. We provide a strongly polynomial algorithm for this problem, called the maximum residual flow problem, and consider various extensions of this basic model. In the second problem, known as the most vital arc problem, the objective is to remove an arc so that the maximal flow on the residual network is as small as possible. Results are also derived which help implement an efficient scheme for solving this problem.
