4   Network Flow Problems
Yet another area of rich applications of graphs (actually digraphs) deals with so called networks and "commodity flows" in them.
This time, the main optimization task is to maximize a flow from the designated source to the designated sink, respecting given constrains - capacities of network arcs.
Brief outline of this lecture
• Networks (weighted directed graphs) and flows in them.
• A network-flow algorithm(s) based on augmenting paths.
• Applications in connectivity, matching, and SDR problems.
4.1   Defining a flow network
The underlying structure of a flow network is a directed graph, with its vertices representing network nodes, and arcs representing the (existing or possible) connections between nodes, c
Definition 4.1. A flow network is a quadruple S — (G,z,s,w) such that
- G is a digraph,
- the vertices z e V(G), s G V(G) are the source and the sink, respectively,
- and w : E(G) —>• i?+ is a positive weighting of the arcs (edges) of G, these weights are called edge capacities.
5
2
Remark: In reality, more than one source or sink may exist in a flow network, but that is not a problem — we simply create a single artificial source and draw arcs from it to all the real sources (even with source capacities).
Notation: For simplicity, we shall write e —>• v to mean that an arc e "comes to" (has its head in) the vertex v, and e ^— f analogically for e "leaving" (having tail in) v. c
Definition 4.2. A network flow, in a flow network 5 — (G, z, s, w),
is an assignment / : E(G) —>• Jig" satisfying (we say / is admissible)
- Ve G E(G) : 0 < /(e) < w(e), (respecting capacities)
- Vv e V(G),u ^ z,s :       f(e) — Y /(e)-        (flow conservation)
The s/ze (value) of a flow / is the quantity ||/|| — Y f(e) ~ Y f(e)- c
Notation: The flow value F and the capacity C of an arc in a picture of a network will be shortly denoted by F/C, respectively.
Remark: Notice the following simple identity
o = e(/(<o-/(*)) = e (e/(<o-e/(<o) = e (e/(<o-e/(<o) •
e££ ijGV  \e<— v e—>^ /        v — z,s  \e<— v e—>v J
What interesting does it tell us? Briefly, that the (opposite) flow value can be analogically defined at the sink s, or more generally at any "z-s cut".
ii/ii = (e   - e / w) = (e   - e / w) •
\e«—e—5-z / \e—>s e-^s /
4.2   Finding the maximum flow value
There exist quite simple and fast algorithms to determine the maximum flow value in a given network.
Problem 4.3. The Max-Flow problem
Given a flow network S — (G, z,s,w), the task is to find a flow f in S from z to s such that the value ||/|| is maximized (among all admissible flows in S). □
Is the depicted flow really maximum possible?
The main question is; how can we certify that no better flow exists in 5?
Fortunately, a nice and simply understandable criterion exists there — notice that there is an "arc cut" between z and s of total value 6, and hence obviously there cannot be a larger flow!
Cut in a network
Definition 4.4. A cut in a flow network S — (G, z, s, w)
is a subset of edges (arcs) C C E(G) such that there is no z^s directed path in G
completely avoiding C (i.e. no directed z^s path existing in G — C).
The size of a cut C is the sum of the capacities of arcs in C, i.e. ||C|| — ^2eeQ w(e).o
Theorem 4.5. The maximum (admissible) flow value in a network S equals the minimum cut size in S.
See the following example with a cut of size 5 (in the middle), and so the flow value 5 is maximum.
4
Remark: Theorem 4.5 is an example of a so called good characterization of a property — not having a larger flow can be certified by showing an obvious constraint, i.e. a cut of the corresponding size.
Residual and augmenting paths
Definition: Consider a flow network S and a flow / in it. A residual z-x path (in S w.r.t. / and source z) is an undirected path in G from the source z to any vertex x, i.e. a sequence of adjacent edges e±, e?, ■ ■ ■, em\
- such that f(ei) < w(ei) if    is directed from z,
- and f(ei) > 0 if    is directed from s. c
The quantity w(ei) — /(ej), or /(e^), resp., is called the residual capacity of edge e^.
□
A residual path is that of strictly positive residual capacities...
residual capacities:
1/2
+ 1
1/1
+1
+2
2/3
2/4
+2
> o
□
Method 4.6. Maximizing flow via residual paths.
The overall idea is really simple;
one should repeatedly enlarge the flow by adding to it along residual paths.
How to augment a residual path.
3/4        1/2        1/1        2/3 2/4
KD
residual capacities: V_y _|_-^ _l_2        +2 > 0
min. residual capacity r = 1 > 0    ~>    augmenting the current flow by +1:
4/4       2/2       0/1        1/3 S/4^
—^ • Kg)
Fact: Augmenting (enlarging) an admissible flow by the minimal residual capacity of a residual z—s path results in an admissible flow, again.
A residual path algorithm
Algorithm 4.7. Ford-Fulkerson's for network flows.
input <   a flow network S — (G, z,s,w); flow f = 0; repeat {
Search (BFS) the graph G to find the set U of those vertices accessible from the source z along residual paths;
if (seU ) {
P = any residual z-s path in S (this P then called an augmenting path); Augment ( "enlarge") f by the minimal residual capacity along P;
}
until ( s g U );
output >   a maximum flow f in S;
output >   a minimum cut in S from U to V(G) — U.
Petr Hliněný,   Fl MU Brno,   2013 10/19 Fl: MAOIO: Network Flows
Proof of Algorithm 4.7:
For any flow / and any cut C in S, it holds ||/|| < ||C||. If the algorithm stops with a flow / in S and a cut C such that ||C|| — ||/||, then it is clear that / is a maximum flow in S. (We have, however, not proved yet that the algorithm stops!)
So to prove that whenever the algorithm stops with /, C, then ||/|| — \\C\\, we use the following schematic picture (in which s does not belong to the "accessible" set U):
/(e) = w(e)
©
U
0
/(e) = 0
Since no further vertex than U is accessible along residual paths, every arc e leaving U has full flow /(e) — w(e), and every arc e entering U has zero flow /(e) — 0. Therefore;
e^U e^rlj e^-U e£C
That is nice, and it remains to argue that ||C|| — ^2e^u f(e) — ^2e^u /(e) — ||/||, finishing the proof. C
Petr Hliněný,  Fl MU Brno, 2013
11/19
Fl: MAÜ1Ü: Network Flows
The proof of Algorithm 4.7 shows several interesting things:
Fact: If we can prove that Algorithm 4.7 stops, we prove also Theorem 4.5.
Fact: If the edge capacities in S are integral, then Algorithm 4.7 always stops.
Corollary 4.8. If the edge capacities in S are integral, then Algorithm 4.7 outputs an integral flow, c
Improved flow algorithms
Generally, one cannot guarantee that Algorithm 4.7 stops, since counterexamples exist with real capacities, but we can do better as follows, c
Algorithm 4.9. Edmonds-Karp's for network flows.
As in Algorithm 4.7, we always enlarge one of the shortest residual paths in G (i.e. find the path P using BFS, cf. Corollary 3.4).
This implementation is guaranteed to stop after 0(\V(G)\ ■ \E(G)\) iterations, so in total computing time 0(\V(G)\ ■ \E(G)\2).
Petr Hliněný,  Fl MU Brno, 2013
12/19
Fl: MAÜ1Ü: Network Flows
Improved flow algorithms, II
Even better, we can use the following "clever" algorithms.
Algorithm 4.10. Dinitz's for network flows (a sketch). We modify Algorithm 4.7 with the following iteration:
• Using BFS, we find all the shortest residual paths in S, creating a "layered" residual network.
• The layered network is then completely saturated in one run.
This implementation makes only 0(\V(G)\) iterations of the main cycle. Total computing time now is 0(\V(G)\2 ■ \E(G)\). c
Algorithm 4.11. MPM "Three Indians" (a sketch).
Same as Algorithm 4.10, except that a layered network is saturated faster, and the total computing time is 0(\V(G)\3).
Petr Hliněný,  Fl MU Brno, 2013
13/19
Fl: MAOIO: Network Flows
4.3   Generalized network flow settings Networks with vertex capacities
In a flow network with vertex capacities (of course, retaining edge capacities as well), the weight function is w : E(G) U V(G) ->• R+
The meaning for admissible flows is that the total sum of incoming flow to any vertex x is not more than w(x). (Differently applicable to the source or the sink, though... )□
Fact. Such a generalized flow network can easily be translated to an ordinary network via "doubling" the capacitated vertices (replacing them with new arcs between the two copies), as follows.
5
5
5
Petr Hliněný,  Fl MU Brno, 2013
14/19
Fl: MAÜ1Ü: Network Flows
Networks with lower capacities
In a flow network with lower capacities, in addition to the weight function w, there is another weight function £ : E(G) —>• Hq~ giving the lower edge capacities.
A flow / is admissible in such a network if 1(e) < /(e) < w(e) for every edge e of the network. : Notice that an admissible flow may not exist in such a lower-capacitated network, c
Algorithm 4.12. Flows in lower-capacitated network
For this kind of a flow network, the solution has two steps.
- First, an admissible circulation is found (with a "back-arc" sz), respecting both the lower an upper bounds £, w. This is done by finding a maximum flow in an artificial network modelling the "surplus" of lower capacities at every vertex...
- Second, this admissible circulation is enlarged by a maximum possible excessive flow from z to s (the capacities are now w(e) — r(e) where r is the circulation found above), c
Multicommodity flows
This is a difficult problem setting reaching beyond the scope of our lecture.
Petr Hliněný,  Fl MU Brno, 2013
15/19
Fl: MAÜ1Ü: Network Flows
4.4   Other applications of network flows Bipartite matching
Definition: A matching in a graph G (bipartite here) is a subset of edges M C E(G) such that no two edges from M share a vertex, c
Algorithm 4.13. Finding maximum matching in a bipartite graph
Given a bipartite graph G with the vertex parts A, B, we construct the following flow network S:
A B
All the edges are implicitly directed from the source towards the sink, and all capacities are 1. We run Algorithm 4.7, and form the resulting matching M by those edges of G having nonzero flow at the end.
Proof of Algorithm 4.13: By Corollary 4.8, the maximum flow found by our algorithm is integral, which now means that each flow unit is 0 or 1. Hence no two edges of M could share a vertex. Conversely, any matching M' gives an admissible flow in S. C
Petr Hliněný,  Fl MU Brno, 2013
16/19
Fl: MAÜ1Ü: Network Flows
Higher graph connectivity
Let us consider a graph G as a generalized (symmetrically-oriented) network with all vertex capacities equal to 1. Then the network flow theorem immediately says:
Corollary 4.14. Let u,v be two vertices of G and k > 0 be an integer. Then there exists at least k internally disjoint u-v paths in G if, and only if, removing any subset of at most k — 1 vertices of G (other than u,v) does not disconnect u from v.
This statement immediately implies Theorem 2.7 (Menger's)l
Petr Hliněný,  Fl MU Brno, 2013
17/19
Fl: MAÜ1Ü: Network Flows
Systems of distinct representatives (SDR)
Definition: Let Mi, M2, ■ ■ ■, Mk be a collection of nonempty sets. A system of distinct representatives (SDR) of the set family {Mi, M2, ■ ■ ■, Mk} is a sequence of pairwise distinct elements (xi,X2, ■ ■ ■, Xk) such that Xj G Mi for i — 1, 2,..., k. c
Theorem 4.15. (Hall) /.et {Mi,M2, ■ ■ ■, Mk} be a family of nonempty sets. Then there exists a system of its distinct representatives if, and only if,
VJC {1,2,...,*:} : |(J
Mi
> \J\
i.e., the union of any subfamily of these sets has at least that many elements as the number of sets in it.
Necessity of Hall's condition in this theorem is obvious, and its sufficiency can be proved by an application of network flows again.
Petr Hliněný,  Fl MU Brno, 2013
18/19
Fl: MAÜ1Ü: Network Flows
Flows in image segmentation
Yet another profitable application of flow networks lies in the computer vision area:
The basic image segmentation problem asks for decomposing a given image into a foreground and a background.
• Let the input consists of a pixel matrix, each pixel carrying two values of likelihood to be in the foreground and in the background. Additionally, separation penalties are assigned to the neighbouring pairs of pixels, c
• The network is constructed by introducing a source z and a sink s such that the arcs from z to the pixels have their capacities equal to the foreground likelihood, and the arcs from the pixels to s have their capacities equal to the background likelihood. Additional bidirectional arcs join the neighbouring pixel pairs.
• A minimal cut in this network then defines the separation between foreground and background parts.
Petr Hliněný,  Fl MU Brno, 2013
19/19
Fl: MAOIO: Network Flows