Flows with vertex and arrow capacities #
Let Q be a finite arrow family with nonnegative capacities cap on its arrows, let s ≠ t be
terminals, and let c v be a nonnegative capacity on every vertex v other than s and t. An
ordinary s–t flow respects the vertex capacities when the total value entering every
nonterminal vertex v is at most c v; by conservation this is also the total value leaving v.
A mixed separator is a pair (X, F) of a vertex set X avoiding the terminals and a set F of
arrows such that every walk from s to t passes through a vertex of X or traverses an arrow of
F; equivalently, deleting X and F leaves no walk from s to t. Its weight is
∑ v ∈ X, c v + ∑ a ∈ F, cap a, counting an arrow of F even when it is incident to a vertex of
X.
This file proves the max-flow/min-cut theorem for these mixed capacities: the value of every flow respecting the vertex capacities is at most the weight of every mixed separator, and some such flow and some mixed separator attain equality, with every arrow value of the flow in any additive subgroup containing all the capacities.
The proof reduces to ordinary flows by vertex splitting (TauCeti.SplitHom). The split network
keeps the capacity cap e on each original arrow, puts c v on the split arrow of each
nonterminal vertex, and the total capacity of all arrows on the split arrows of the terminals
(TauCeti.mixedSplitCapacity); its terminals are the exit s⁺ of s and the entrance t⁻ of
t. The flows respecting the vertex capacities correspond exactly to the ordinary s⁺–t⁻ flows
of the split network, with the same values on the original arrows and the same value
(TauCeti.Flow.mixedSplitEquiv). A cut of the split network is mapped to the mixed separator
formed by its crossing split arrows and its crossing original arrows, of weight equal to the cut
capacity, and a mixed separator is mapped to a cut whose crossing arrows it contains. The two maps
between cuts and separators do not depend on the capacities of the terminal split arrows; only the
correspondence with all flows uses that those capacities bound the traffic through the terminals.
Taking every vertex capacity to be the total capacity of all arrows imposes no constraint
(TauCeti.Flow.respectsVertexCapacity_arrowSum), so ordinary max-flow/min-cut is the special case
in which mixed separators may as well contain no vertices.
Main definitions #
TauCeti.IsMixedSeparator X F s t: every walk fromstotmeets the vertex setX, which avoidssandt, or the arrow setF.TauCeti.Flow.RespectsVertexCapacity f c: the flowfcarries at mostc vinto every vertexvother than its terminals.TauCeti.mixedSplitCapacity cap c s t: the capacities of the split arrows in the reduction.TauCeti.Flow.mixedSplitEquiv: the correspondence between flows respecting the vertex capacities and ordinary flows of the split network.
Main results #
TauCeti.SplitHom.isMixedSeparator_cutVertices_cutArrows: the arrows leaving a cut of the split network form a mixed separator.TauCeti.SplitHom.arrowSum_assignment_compl_eq_weight: the capacity of a cut of the split network equals the weight of that mixed separator.TauCeti.IsMixedSeparator.exists_cutVertices_subset: every mixed separator contains the arrows leaving some cut of the split network.TauCeti.Flow.RespectsVertexCapacity.val_le: weak duality between flows and mixed separators.TauCeti.Flow.exists_respectsVertexCapacity_val_eq_memandTauCeti.Flow.exists_respectsVertexCapacity_val_eq: the max-flow/min-cut theorem for mixed vertex and arrow capacities, with integrality in an additive subgroup.
References #
- L. R. Ford, D. R. Fulkerson, Flows in Networks, Princeton University Press, 1962.
- A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Springer, 2003.
Mixed separators #
A mixed separator between s and t is a pair of a vertex set X, containing neither s
nor t, and a set F of arrows, each recorded with its endpoints, such that every walk from s
to t passes through a vertex of X or traverses an arrow of F. Equivalently, no walk from s
to t survives the deletion of the vertices of X and the arrows of F.
Instances For
Every walk from s to t meets a mixed separator.
The terminals of a mixed separator are distinct, since the walk of length zero meets no vertex set avoiding its terminal and no arrow set.
Enlarging a mixed separator, while keeping its vertices away from the terminals, gives a mixed separator.
A mixed separator without arrows is a vertex set avoiding the terminals whose deletion leaves
t unreachable from s.
Cuts of the split network and mixed separators #
Cuts give mixed separators. For distinct terminals and a vertex set S of the split
network containing the exit of s but not the entrance of t, the vertices whose split arrows
leave S and the original arrows leaving S form a mixed separator between s and t.
Cuts give mixed separators of equal weight. For a vertex set S of the split network
containing the exit of s but not the entrance of t, and split capacities φ agreeing with the
vertex capacities c away from the terminals, the cut capacity of S equals the weight of the
mixed separator formed by the vertices whose split arrows leave S and the original arrows leaving
S (TauCeti.SplitHom.isMixedSeparator_cutVertices_cutArrows).
Mixed separators give cuts. Every mixed separator (X, F) between s and t contains the
crossing arrows of some vertex set of the split network containing the exit of s but not the
entrance of t: the vertices of X include those whose split arrows leave it, and F includes the
original arrows leaving it.
Every mixed separator (X, F) gives a vertex set of the split network containing the exit of
s but not the entrance of t, whose cut capacity is at most the weight of (X, F), whenever the
capacities of the vertices of X and of the arrows of F are nonnegative.
Flows respecting vertex capacities #
The capacities of the split arrows in the reduction of mixed capacities to arrow capacities:
the vertex capacity c v on the split arrow of every vertex v other than s and t, and the
total capacity of all arrows on the split arrows of s and t, which bounds the traffic through
the terminals.
Instances For
An ordinary s–t flow respects the vertex capacities c when the total value entering
each vertex v other than s and t is at most c v. By conservation, this is also the total
value leaving v.
Instances For
A flow respecting the vertex capacities carries at most c v into each nonterminal vertex
v.
Every flow respects the vertex capacities equal to the total capacity of all arrows.
Vertex splitting for mixed capacities. For distinct terminals, the ordinary s–t flows
respecting the vertex capacities c correspond to the ordinary s⁺–t⁻ flows of the split
network with the capacities cap on original arrows and mixedSplitCapacity cap c s t on split
arrows. A flow keeps its values on the original arrows, and its split arrow at each vertex other
than t carries the value entering that vertex.
Instances For
The split arrow of a vertex other than the sink carries the value entering that vertex.
The split arrow of the sink carries the value leaving it.
The correspondence preserves values.
Weak duality for mixed capacities. The value of an ordinary flow respecting the vertex
capacities c is at most the weight of every mixed separator.
The max-flow/min-cut theorem for mixed capacities #
Max-flow/min-cut for mixed capacities, with integrality. For distinct terminals,
nonnegative arrow capacities and nonnegative capacities on the nonterminal vertices, all lying in an
additive subgroup H, some ordinary flow respecting the vertex capacities, with every arrow value
in H, has value equal to the weight of some mixed separator. By weak duality
(TauCeti.Flow.RespectsVertexCapacity.val_le), this flow is maximum among the flows respecting the
vertex capacities and this separator has minimum weight.
Max-flow/min-cut for mixed capacities. For distinct terminals, nonnegative arrow capacities and nonnegative capacities on the nonterminal vertices, some ordinary flow respecting the vertex capacities has value equal to the weight of some mixed separator.