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.