Max-flow/Min-cut
l s-t flow: edge-disjoint packing of s-t paths
l s-t cut: a cut separating s and t
l [FF]: s-t max-flow = s-t min-cut
» max-flow saturates all s-t min-cuts
» most efficient way to find s-t min-cuts
l [GH]: min-cut is “all-pairs” s-t min-cut
» find using n flow computations