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.

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.