Show a reduction of max flow to min cost (not min cost max flow!!)
$\begingroup$
$\endgroup$
1
-
2$\begingroup$ Please do not make destructive edits to your question that make it harder to understand what you are asking. $\endgroup$– D.W. ♦May 3, 2022 at 23:02
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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$.
-
$\begingroup$ 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$. $\endgroup$– StevenMay 2, 2022 at 16:44
-