A Min Flow Max Cut Theorem

D

Andrew Kitchen

epartment of Computer Science
ySchool of Computer Science and Information Technolog
Rochester Institute of Technology
Rochester, New York 14623
USA

T

T

ABSTRAC

his paper presents a dual of the Max Flow Min Cut Theorem. The result, although s
u
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 -
l
deduce Bogart's Theorem on the representation of a finite poset as a union of linear y ordered sets.

1. Introduction.

Consider a network of pipes joining a set of intakes (the source) to a separate set of outlets (the e
n
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
c
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 ,
a
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

m
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.

r
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 e
t
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

F
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

u
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 e
s
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.