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 Edit


  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.