The Maximum Flow Problem with Negative Capacities or Flows

Abstract

The maximum flow problem is a classic network flow problem, and the dual relationship between the problem and the minimum cut problem is one of the most famous conclusions in network flow theory. In this paper, we expand the problem from the conventional network with only non-negative capacities and non-negative flows to a generalized one with negative capacities or negative flows, and test that the generalized network may have broader applications. In the network, we discover that the maximum flow value may be not equal to the minimum cut capacity, and the maximum flow problem and the minimum cut problem are not dual of each other. We explore a new type of cut set and name it as critical cut. The critical cut capacity is equal to the maximum flow value, and the critical cut problem and the maximum flow problem are dual of each other in the conventional and generalized networks. We design an algorithm to compute maximum flow and critical cut in the network with negative capacities or negative flows.