1
$\begingroup$

So the wikipedia page gives the following linear programs for max-flow, and the dual program :

enter image description here

While it is quite straight forward to see that the max-flow linear program indeed computes a maximum flow (every feasable solution is a flow, and every flow is a feasable solution), i couldn't find convincing proof that the dual of the max-flow linear program indeed is the LP of the min-cut problem.

An 'intuitive' proof is given on wikipedia, namely : $d_{uv}$ is 1 if the edge $(u,v)$ is counted in the cut and else $0$, $z_u$ is $1$ if $u$ is in the same side than $s$ in the cut, and $0$ if $u$ is in the same side of the cut than $t$

But that doesn't convince me a lot, mainly why should all the variables be integers, while we don't have integer conditions ?

And in general, do you have a convincing proof that the dual of the max-flow LP indeed is the LP formulation for min-cut ?

Edit : Ok i found a proof here http://theory.stanford.edu/~trevisan/cs261/lecture15.pdf , however it only gives a probabilistic way to build the cut from the variables assignement of the LP.

$\endgroup$
4
  • 1
    $\begingroup$ The dual of max-flow is not the LP formulation for min-cut, it is a relaxation for min-cut. It is an LP without restricting the variables to be integers (that's what relaxation means here) and such that its minimum is the minimum capacity of a cut. The latter is the content of the Max-Flow Min-Cut theorem. You can find these theorems in many books in linear programming, for example in Chvatal's. $\endgroup$
    – plop
    Aug 5 '20 at 3:00
  • 1
    $\begingroup$ The variables of the dual don't need to be integers, neither for feasible, nor for optimal solutions. Instead, what is true is that there are feasible solutions that are integral and optimal solutions that are integral. This is the content of the Integrality Theorem. $\endgroup$
    – plop
    Aug 5 '20 at 3:03
  • $\begingroup$ Is there recent proof of the integrality theorem ? In chvatal book it is said that the integrality theorem holds for any linear program $Ax=b$ where $b$ has integer coefficient, but the proof seems to use notions specifically defined in the book and not used elsewhere. $\endgroup$
    – lairv
    Aug 5 '20 at 22:39
  • $\begingroup$ There are many proofs. In Chvatal there are at least two different arguments. One is the very application of the optimization algorithms, which move only along integral points. Another is following a particular set of feasible solutions, which are also integral. Now, what you said is not what is said in Chvatal's book. They said that for a transport problem (or whichever name they call it), if $b$ is integer then there are feasible integer solutions etc. The first assumption implicitly imposes conditions on $A$. $\endgroup$
    – plop
    Aug 6 '20 at 1:12
1
$\begingroup$

We can write the constraints on the $d_{uv}$ as follows: $$ d_{uv} \geq z_u - z_v, z_v - z_u $$ $$ d_{sv} \geq 1 - z_v $$ $$ d_{ut} \geq z_u $$ Since we are minimizing $\sum d_{uv} c_{uv}$ and $c_{uv} > 0$, this means that we want to minimize each individual $d_{uv}$, and so in fact $$ d_{uv} = |z_u - z_v| $$ $$ d_{sv} = 1 - z_v $$ $$ d_{ut} = z_u $$ If we put $z_s = 1$ and $z_t = 0$, then the formula $$ d_{uv} = |z_u - z_v| $$ holds for all $u,v$.

We can think of $z_v$ as specifying the position of the vertices on the real line. We are penalized $c_{uv} |z_u - z_v|$ for each edge $(u,v)$. Furthermore, $z_s = 1$ and $z_t = 0$. From this description, it is evident that there is no reason to put any vertex beyond the interval $[0,1]$.

If $z_v \in \{0,1\}$ for all $v$, then we can think of the $z_v$ as specifying a cut: one side (which includes $s$) consists of all $v$ such that $z_v = 1$, and the other side (which includes $t$) consists of all $v$ such that $z_v = 0$. If we allow general $z_v \in [0,1]$, then we can think of it as a "fractional cut".

It is natural to ask whether fractional cuts are better than cuts. It turns out that they aren't. The simplest way to see this (same proof as in Luca Trevisan's lecture notes) is to construct the cut randomly: choose a threshold uniformly at random in $[0,1]$, and use it to partition the vertices into those left of the threshold and those right of the threshold. The probability that two vertices $u,v$ are in different sides of the cut is exactly $|z_u - z_v|$, and so the expected weight of the cut is $\sum_{uv} c_{uv} |z_u - z_v|$.

This is a very simple example of the metric method in the design of algorithms.

$\endgroup$

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.