The minimum saturated flow problem in emergency networks

A flow in network N is said to be saturated if its value cannot be enhanced any more by increasing flows along the forward direction. In a traffic jam or in a situation of emergency evacuation, the network is often blocked by a saturated flow. Clearly, the smaller the value of the saturated flow, the worse is the performance of the network. This gives rise to the minimum saturated flow problem in network analysis. In this paper we first show that the problem is NP-hard. Then, the relation between minimum saturated flows and maximum flows, as well as results in the algorithmic aspect, are presented.