Minimum Cut Problem

This is an alternate formulation to the Max Flow Problem.

• We want to remove some edges from the graph such that after removing the edges, there is no path from s to t.
• The cost of removing e is equal to c(e).
• The minimum cut problem is to find a cut with minimum total cost.

Theorem: Minimum Cut = Max Flow

Since we know the max flow, we can use the Residual Graph to find the min cut.

Algorithm

Steps:

1. Mark all nodes reachable from S. Call this set of reachable nodes A.
2. Now separate these nodes from the others. Cut edges going from A to V - A
3. Now look at the original graph and find the cut.