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.
Best Answer
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.