# Show a reduction of max flow to min cost

Show a reduction of max flow to min cost (not min cost max flow!!)

• Please do not make destructive edits to your question that make it harder to understand what you are asking.
– D.W.
May 3, 2022 at 23:02

Consider a graph $$G$$ and let $$s$$ (resp. $$t$$) be the source (resp. target) vertex for your max-flow problem. Let $$U$$ be an upper bound to the max flow (for example the sum of the capacities of the edges leaving $$s$$, or the sum of the capacities of the edges entering $$t$$).
Construct an instance of min-cost flow where you want to send $$U$$ units of flow from $$s$$ to $$t$$ and the graph $$G$$ is modified as follows:
• All edges of $$G$$ have cost $$0$$
• Add a new edge $$(s,t)$$ with cost $$1$$ and capacity $$U$$.
If $$x$$ is the cost of a min-cost flow on this graph, then the max flow in $$G$$ is $$U-x$$.
• The answer is showing how to convert a max-flow problem to a min-cost flow problem (which should be your question, as I understand it). Each unit of flow sent "through" $G$ is "free". Each unit of flow sent through the new edge $(s,t)$ costs $1$. Therefore it is convenient to send as much flow as possible through $G$. If the optimal cost of sending $U$ units of flow from $s$ to $t$ is $x$, then there are exactly $x$ units that could not be sent through $G$. This means that the max-flow from $s$ to $t$ in $G$ is exactly $U-x$. May 2, 2022 at 16:44