Mincut problem

Def. A st-cut (cut) is a partition of the vertices into two disjoint sets, with s in one set A and t in the other set B.

Def. Its capacity is the sum of the capacities of the edges from A to B.

Minimum st-cut (mincut) problem. Find a cut of minimum capacity.

Maxflow problem

Def. An st-flow (flow) is an assignment of values to the edges such that:

• Capacity constraint: 0 <= flow <= capacity
• Local equilibrium: inflow == outflow at every vertex (except s and t).

Maximum st-flow (maxflow) problem. Find a flow of maximum value. (from s to t)

Mincut and maxflow are dual problem (the same problem)!

Ford-Fulkerson Algorithm

1. Start with 0 flow.
2. While there exists an augmenting path:
   1. find an augmenting path
      1. Shortest path (BFS)
      2. Fattest path (priority queue)
   2. compute bottleneck capacity
   3. increase flow on that path by bottleneck capacity