Lesson 4

Theorem. Let \((L',R')\) be a minimum cut in \(G\). Then \(L' \setminus \{s\}\) is the optimal set of projects.

Proof. The minimum cut in \(G\) has capacity at most \(C=\sum_{i \colon p_i > 0}p_{i}\), because this is the capacity of the cut \(\{s\}\).

There is a natural bijection between feasible sets of projects \(A\) and cuts \((L,R)\) of finite capacity: \[A \leftrightarrow L=A \cup \{s\} \ .\] Indeed, if set \(A\) is feasible, then no constraint edge \((i,j)\) is in the cut \(L=A \cup \{s\}\). Conversely, if cut \((L,R)\) has finite capacity, then the project set \(A=L \setminus \{s\}\) is feasible.

Now we show that \[\operatorname{profit}(A)=C-\operatorname{capacity}(L,R) \ .\] Thus, a cut of minimum capacity corresponds to a project set of maximum profit.

So, let \(L=A \cup \{s\}\). In the cut \((L,R)\), the edges are: \((s,i)\) where \(i \not \in A\) and \(p_{i}>0\), and \((i,t)\) where \(i \in A\) and \(p_{i}<0\). So: \[\begin{align*}\operatorname{capacity}(L,R)&=\sum_{i \not \in A, p_i>0}p_{i}-\sum_{i \in A, p_i<0}p_{i}=\\&=\left(C-\sum_{i \in A, p_i>0}p_{i}\right)-\sum_{i \in A, p_i<0}p_{i}=\\&=C-\operatorname{profit}(A) \ .\end{align*}\]◼