Min-cost-flow to max-flow

Question

Is there a reduction from the min cost flow problem to the max-flow problem? Or viceversa? I would like to use a min cost flow algorithm to solve a max-flow problem.

Answer 1

Sorry I think I misunderstand the question the first time. Yes, Minimum Cost is a special case for max flow. Rather than max flow, min cost assumes that after going through each edge, there is a cost to the flow. Therefore, if you set the cost at each edge to be zero, then min cost is reduced to the max flow.

Edit:

Since min cost problem needs a pre-defined required flow to send to begin with. You will need to run the above algorithm (with cost of edge c(u, v) = 0) for multiple times to search for the maximum value. For a given range of values, binary search can be used to more efficiently locate the max

Do you mean Min Cut Max Flow? (Edit: I do not think you meant this, but this is the basis of proving max flow, worth looking at if you have not) I will be easier to understand if you drop a graph and do a min cut yourself.

Answer 2

Add a cost (per unit flow) of -1 to each edge, then use your minimise cost algorithm. That will maximise the flow.

Answer 3

The accepted answer may be practical. Proofing that Max-Flow is a special case of Min-Cost-Flow there is another possibility. My solution takes one iteration of the minimum-mean-cycle-cancelling algorithm in O(m^3 n^2 log n) (cause c is not conservative):

1. set c(e) = 0 for all edges in G
2. add edge (t,s) with inf capacity and c((t,s)) = -1
3. start MIN-MEAN-CYCLE-CANCELLING on modified graph G'

correctness: Algorithm is searching for residual circles with negative weight. As long as there is an augmentive path from s to t there are negative weighted residual circles.