ABSTRACT
This chapter discusses the duality twice: directly from the classical algorithm by Ford and Fulkerson, and from linear programming duality. The maximum flow problem is to send as much as possible through a network from a given node s to a given node t, while respecting upper bounds on the arcs. And indeed, Ford and Fulkerson's earliest technical report, dated 1954, proved the maximum flow/minimum cut duality. The minimum cut problem is a natural model for minimizing the cost of interdiction of a transportation network. Then the minimum cut tells us which arcs to destroy to minimize our cost. Weak duality between maximum flow and minimum cut is fairly easy to understand. The dual to maximum flow from s to t is the minimum cut between s and t, which is the minimum possible sum of arc capacities from S to T of a partition of the nodes such that and.
