Max flow min cut from duality

Question

I have been having some trouble deriving the max flow min cut theorem from duality, which I was told is possible. To begin with, I need to cast the problem into the form "maximize $\langle c, x\rangle$ subject to the constraint $Ax\le b$ and $x\ge0$. This needs to be done in such a way so that the dual of this LP, i.e. minimize $\langle b, x\rangle$ subject to the constraints $A^t y\ge c$, and $y \ge 0$, "is" the min cut problem.

Of course, it is not literally the min cut problem, being a problem lying within a Euclidean space. But it's not even that there exists a bijection between the set of feasible points for this second (dual) problem and min cut that preserves the ordering on the objective values. In fact, min cut is an optimization problem over finitely many points, namely $2^{|V|}$ of them. A friend told me what may be intended is that the vertices of the polytope constituting the feasible region are in bijection with the cuts. Optimal values must occur on vertices. Even if so, this seems only as much of an equivalence as saying "they're equivalent because the optimal values are always the same."

But even this weak "equivalence" is one I cannot see. Choose an enumeration $e_1, \dots, e_{|E|}$ of the edges in a graph $V(G), E(G)$ and an enumeration of the vertices $v_1, \dots, v_{|V|}$. Max flow will be identified with the LP I construct below with the map associating each flow to a vector in Euclidean space of dimension $|E|$ I will use this identification freely without further remark.) $c(e)$ are the capacities, $s, t$ the source and sink respectively, $h(e)$ the head and $t(e)$ the tail of an edge.

To start with, I force "max flow" into the form above by defining a vector $c:=\sum_{e:t(e)=s}1_{e}-\sum_{e:h(e)=s}1_{e}$. Then I take $A=(a_{ie})$ where $e\in E$ and for $1\le i \le |E|$ we have $a_{ie}=\delta_{e_ie}$, for $|E|<i\le |E|+|V|-2$ we have $a_{ie}=1$ if $e$ points away from $v_{i-|E|}$, $-1$ if it points towards, and $0$ otherwise. Then we set the rest of the $a_{ie}=-a_{i-|V|+2\,e}$. We set $b$ to be the capacities in the first $E$ slots and then $0$ after that.

Effectively, I use $|E|$ dimensions to write the constraints of capacity, and then $|V|-2$ dimensions to write the constraints of flow in one inequality, and the rest for the other inequality. I don't see where to go now. Particularly, the reason I believe I am stuck is manyfold, but mainly because once I transpose $A$ I get $|E|$ constraints, and I have no idea why that polytope even determines $2^{|V|}$ vertices.

Answer 1

While your linear program is a valid formulation of the max flow problem, there is another formulation which makes it easier to identify the dual as the min cut problem.

Let $(G,u,s,t)$ be a network with capacities $u: E(G) \rightarrow \mathbf{R}^+$, source vertex $s$ and sink vertex $t$. Let $P$ be the set of all simple $(s,t)$-paths in $G$. Suppose we have one variable $x_p$ for each possible $p \in P$, which represents how much of the flow is being routed along that path. Then the linear program using these variables becomes

$$ \begin{array}{rcclr} \text{max} & \sum_{p \in P} x_p & & & \\ \text{subject to} & \sum_{p \ni e} x_p & \leq & u(e) & \forall e \in E \\ & x_p & \ge & 0 & \forall p \in P \end{array} $$

The first inequalities assure that the capacity of every edge is not violated, and the sum there involves every path containing a certain edge. The second set of inequalities just forces the flow of every path to be non-negative. This formulation has a (possibly) exponential number of variables, but the point here is to reduce the number of constraints, so that the dual becomes easier. Using the flow decomposition you can check that there exists a feasible flow for your LP if and only if there exists a feasible flow with the same cost for my LP, so both formulations are equivalent.

The dual of the new LP has a variable $y_e$ for every edge in $E$, and has the form

$$ \begin{array}{rcclr} \text{min} & \sum_{e \in E} u(e) y_e & & & \\ \text{subject to} & \sum_{e \in p} y_e & \ge & 1 & \forall p \in P \\ & y_e & \ge & 0 & \forall e \in E \end{array} $$

The interpretation here is that every edge has a non-negative weight and for every $(s,t)$-path the sum of its edges must be at least $1$. This is a relaxation of the min cut problem. In fact, if you take any $(s,t)$-cut $F \subseteq E$ and consider the characteristic vector $v^F \in \{0,1\}^{E}$ such that $v^F_e = 1$ if and only if $e \in F$; then this vector is feasible for the dual LP with value equal to the value of the cut $F$. So the optimum of the LP is a lower bound for the min cut problem in the network.

Using the duality theorems for linear programming you could prove the max flow min cut theorem if you could prove that the optimum in the dual problem is exactly the min cut for the network, but this needs a little more work. You can check the details in this lecture.