Graph Theory37 sections · 1633 units
Open in Course

Minimum s-t Cut

(Cheapest way to disconnect)

The minimum ss-tt cut is the cut with the smallest capacity among all ss-tt cuts. It is the cheapest way to disconnect ss from tt. There might be many different cuts, but this one has the lowest cost. You are looking for the bottleneck: which edges, when removed, stop all flow with the least total capacity lost?

This is the network's vulnerability point. This cut represents the weakest point in the network between ss and tt. Attack this cut, and you break the connection most efficiently.