-1
$\begingroup$

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

$\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

1 Answer 1

0
$\begingroup$

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$.

$\endgroup$
2
  • $\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$
    – Steven
    May 2, 2022 at 16:44
  • $\begingroup$ Please do not vandalize the answer. $\endgroup$
    – Steven
    May 3, 2022 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.