I have been trying to look this up, and I could only find a min cost flow to max flow transformation on the internet. Apparently, this transformation can be done by setting the costs to 0. Another source mentioned setting the costs to -1.

My question is, when formulating the max flow problem as a min cost flow problem:

  • What are the balances of the vertices going to be? I'm quite sure balances of all vertices are going to be 0, except for the source and sink. Unfortunately, there is no way for us to find this value beforehand, so a way to solve this would be to add an edge from the sink to the source - then we can set their balance to 0

  • What are the costs of the edges going to be? 0 does not make much sense to me, as we would be effectively minimizing 0. -1 seems to make much more sense to me, but I am not really sure.

  • $\begingroup$ i'm not positive, but I think max flow is just a sub-routine of the dual to min-cost flow? $\endgroup$ – Chill2Macht May 2 '16 at 16:26
  • $\begingroup$ I think you misread the Wikipedia article, because it says that an arbitrary max flow problem can be made into a min-cost flow problem by setting the costs to zero. It's the other direction (making a min-cost flow a max flow problem) that can't be done in general. $\endgroup$ – Chill2Macht May 2 '16 at 16:36
  • $\begingroup$ Right, since min-cost flow is short for min-cost maximum flow, so a maximum flow probably can always be formulated as a min-cost maximum flow problem by setting the costs to zero, but the other direction is not true in general; the min-cost maximum flow problem is in general more complicated. $\endgroup$ – Chill2Macht May 2 '16 at 16:38

You can do this by adding an edge from the sink to the source, with cost $-1$ and an infinite capacity. The other edges have $0$ costs.

The minimum cost flow will try to send as many units of flows from the sink to the source, as it is the only edge with a negative cost. This is precisely what you need for a maximum flow problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.