How do you find the maximum flow on a digraph where capacities may be negative?

Question

Ford-Fulkerson and Edmonds-Karp et. al. start with a zero flow and augment it until it can't be augmented any more. In the case of positive capacities; however, the initial zero flow is guaranteed to be both a legal flow and a flow that satisfies the capacity constraints.

With negative capacities, a flow assignment of all zeroes will not satifisy the capacity constraints so can't then be augmented into a maximum flow.

I've read people on the internet suggest that max flow with negative capacities can be solved as two max flow problems, but haven't been able to figure out how to do it...

Answer 1

Say you have a capacity constraint on an edge from u to v of -3, what does this mean?

Well, by definition, it means that you can't push more than -3 units of flow from u to v; meaning the flow from u to v could be, for example, -5, -4, or -3. If we posit, as is common, that flow of -x from u to v is the same as flow of x from v to u then we see these example flows of -5 or -4 or -3 would translate to flows of 5 or 4 or 3 from v to u and, further, that the flow from v to u could not be less than 3.

Thus we see a maximum capacity of -x from u to v is equivalent to minimum capacity constraint of x from v to u and the problem of handling negative capacity constraints in a max flow computation therefore reduces to the problem of handling both maximum and minimum positive-only capacities.

One can handle minimum and maximum capacities by first finding a feasible flow on the graph, a flow that satisfies flow rules and capacity constraints but that is not necessarily a maximum flow -- this can be done by finding a "circulation" on a specially constructed graph derived from the original graph, and then turning the feasible flow into a max flow by solving a max flow problem. This technique is discussed in detail at the following link: max flow slides