Augmenting paths and the optimality of flows #
A bounded s–t assignment f is maximum when no bounded s–t assignment has a larger
value. An augmenting walk for f is a walk from s to t in the residual network of f that
traverses only residual arrows of positive capacity, so the sink is positively reachable from the
source for the residual capacities. This file proves the augmenting-path optimality criterion of
Ford and Fulkerson: for distinct terminals the following are equivalent.
fis maximum.- There is no augmenting walk for
f. - The value of
fequals the cut bound of some vertex set containingsbut nott.
If an augmenting walk exists, then augmenting along an augmenting path inside it by its bottleneck
increases the value. If there is none, then no residual arrow of positive capacity leaves the set
of vertices positively reachable from s, so by the residual cut gap identity
TauCeti.BoundedFlow.cutBound_sub_val the value equals the cut bound of that set. Weak duality
turns the equality of value and cut bound into maximality. The same criteria hold for ordinary
flows, with cut capacities in place of cut bounds.
These criteria hold over every linearly ordered additive commutative group of coefficients. They
do not by themselves give the existence of a maximum flow, which needs a terminating choice of
augmentations. One augmentation step, along an augmenting walk by its bottleneck, is the relation
TauCeti.Flow.AugmentsTo; a flow between distinct terminals is maximum exactly when no step
starts from it.
Main definitions #
TauCeti.BoundedFlow.IsMaximumandTauCeti.BoundedFlow.IsMinimum: boundeds–tassignments of largest and smallest value, exchanged by terminal swap.TauCeti.Flow.IsMaximum: an ordinarys–tflow of largest value.TauCeti.Flow.AugmentsTo: one augmentation step, along an augmenting walk by its bottleneck.
Main results #
TauCeti.BoundedFlow.exists_val_lt_of_positiveReachable: augmentation along an augmenting walk increases the value.TauCeti.BoundedFlow.val_eq_cutBound_of_not_positiveReachable: without an augmenting walk, the value equals the cut bound of the vertices positively reachable from the source.TauCeti.BoundedFlow.tfae_isMaximumandTauCeti.Flow.tfae_isMaximum: the augmenting-path optimality criterion for boundeds–tassignments and for ordinary flows.TauCeti.Flow.isMaximum_iff_forall_not_augmentsTo: a flow is maximum exactly when no augmentation step starts from it.
References #
- L. R. Ford, D. R. Fulkerson, Maximal flow through a network, Canadian J. Math. 8 (1956).
- A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003, Theorem 10.1 and Corollary 10.1a.
A bounded s–t assignment is maximum when it maximizes the value among all bounded
s–t assignments for the same bounds.
Instances For
When the terminals coincide, every bounded assignment is maximum.
A bounded terminal assignment is minimum when no other feasible assignment has smaller terminal value. No sign condition is imposed on that value.
Instances For
When the terminals coincide, every bounded assignment is minimum.
All minimum bounded terminal assignments have the same value.
All maximum bounded s–t assignments have the same value.
Exchanging the terminals exchanges minimum and maximum assignments.
Exchanging the terminals exchanges maximum and minimum assignments.
A bounded terminal assignment attaining a lower cut bound is minimum.
A bounded s–t assignment whose value equals the cut bound of a vertex set containing s
but not t is maximum.
If a bounded s–t assignment has no augmenting walk, then its value equals the cut bound of
the set of vertices positively reachable from the source for its residual capacities.
Augmentation. If the sink of a bounded s–t assignment between distinct terminals is
positively reachable from the source for its residual capacities, then augmenting along an
augmenting path by its bottleneck gives a bounded s–t assignment of larger value.
A maximum bounded s–t assignment between distinct terminals has no augmenting walk.
Augmenting-path optimality criterion. For a bounded s–t assignment f between distinct
terminals, the following are equivalent: f is maximum; there is no augmenting walk, that is, the
sink is not positively reachable from the source for the residual capacities of f; and the
value of f equals the cut bound of some vertex set containing s but not t.
A bounded s–t assignment between distinct terminals is maximum exactly when it has no
augmenting walk.
A maximum bounded s–t assignment between distinct terminals attains the cut bound of some
vertex set containing s but not t.
A bounded terminal assignment is minimum exactly when its residual network has no positive path from the sink to the source.
A minimum bounded terminal assignment attains a lower cut bound.
Ordinary flows #
An ordinary s–t flow is maximum when it maximizes the value among all ordinary s–t
flows for the same capacities.
Instances For
An ordinary flow is maximum among ordinary flows exactly when it is maximum among all bounded assignments with zero lower bounds: a bounded assignment of larger value has positive value, so it is itself an ordinary flow.
Augmenting-path optimality criterion for ordinary flows. For an ordinary s–t flow f
between distinct terminals, the following are equivalent: f is maximum; there is no augmenting
walk for f; and the value of f equals the capacity of the arrows leaving some vertex set
containing s but not t.
An ordinary s–t flow between distinct terminals is maximum exactly when it has no
augmenting walk.
A maximum ordinary s–t flow between distinct terminals saturates some cut: its value
equals the capacity of the arrows leaving some vertex set containing s but not t.
Augmentation steps #
f.AugmentsTo g when the flow g arises from f by one augmentation step: augmentation by
its bottleneck along an augmenting walk of f, a residual walk from s to t that traverses at
least one arrow, traverses no arrow twice, and has positive residual capacity on every arrow.
Instances For
Augmentation by the bottleneck along an augmenting walk is an augmentation step.
An augmentation step between distinct terminals strictly increases the value.
An augmentation step preserves values in an additive subgroup that contains the capacities.
An ordinary flow between distinct terminals is maximum exactly when no augmentation step starts from it.