A Min Flow Max Cut Theorem
epartment of Computer Science
ySchool of Computer Science and Information Technolog
Rochester Institute of Technology
Rochester, New York 14623
his paper presents a dual of the Max Flow Min Cut Theorem. The result, although
similar in proof to its better known relative, is interesting because the circumstance nder which it holds shed light on the nature of minimal flows. As a corollary, we -
deduce Bogart's Theorem on the representation of a finite poset as a union of linear y ordered sets.
Consider a network of pipes joining a set of intakes (the source) to a separate set of outlets (the
sink), so that liquid flows from the intakes, through the network, to the outlets. A cross-section of th etwork, separating the intakes on one side from the outlets on the other, is called a cut. A minimal t
cut is one that, roughly speaking, slices through a set of pipes whose combined capacity is minimal. I an be shown that if we attempt to force as much liquid as possible through the system, the maximal ,
flow possible is equal to the capacity of a minimal cut. An abstraction and generalization of this result pplied to a network of nodes joined by directed arcs, is known as the Max Flow Min Cut Theorem for
a volume-conserving flow through a network, [FORD56, BOND76, NEMH88]. This theorem, in its ost general form, does not require that the source and sink be sets of intakes and outlets, respectively.
Both the source and the sink may contain intakes and outlets, as well as nodes that both deliver and eceive the flow.
In this paper, we prove a dual of the Max Flow Min Cut Theorem. We place a threshold on each
arc in the network, and require that for a flow through the network, the flow along any arc exceed th hreshold for that arc. Then, we prove that the minimal allowable flow equals the combined thresholds
of the arcs sliced by a maximal cut. This result has some intrinsic interest, in part because a ``Min low Max Cut'' theorem cannot hold under as general circumstances as its dual. This is due to the fact
that lower bounds on the flows cannot prevent such excesses as unbounded backward flow and nbounded recirculating flows (``turbulence''). See figures 1 and 2; the labels indicate the volume of the flow along each arc and the arrows define its direction.
>From this theorem we deduce a result that describes the decomposition of an acyclic graph into a union of a minimum number of directed paths. Bogart's Theorem follows as a direct corollary.
In the next section, we give definitions, and prove necessary and sufficient conditions for the
existence of minimal flows. In section 3, we prove the main result of the paper. Section 4 presents th tructure theorem for acyclic graphs, and the final section applies this result to the network whose vertices are the points of a finite poset, G, and whose arc set is the immediate successor relation on G.