6 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. Fl: MA010: Network Flo 6.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 6.1. A flow network is a quadruple S = (G, z, s,w) such that - G is a digraph, - the vertices z G V (G), s G V (G) are the source and the sink, respectively, - and w : E(G) —> R+ is a positive weighting of the arcs (edges) of G, these weights are called edge capacities. 4 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!). -*etr Hlinený, hl MU Brr Fl: MAOIO: Network Flo 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 <— -y analogously for e "leaving" (having tail in) v. Definition 6.2. A network flow, in a flow network S = (G, z, s,w), is an assignment / : E(G) —> Jig" satisfying (we say / is admissible) - VeG E{G) : 0 -u e<—v The s/ze (value) of a flow / is the quantity ||/|| = J2 /(e) — E /(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. 2/5 2/2 etr Hlinený, Fl MU Br Fl: MAOIO: Network Flo So what is the value of the depicted flow? 5 Remark: Notice the following simple identity o=e (/w - m=y,(j: ™ - e f (A = y,(j: ™ - e ^) • e(zE v(zV \e<—v e—fv / v = z,s \e<—v e—fv / What interesting does it tell us? Briefly, that the (negative) flow value can be analogously defined at the sink s. = ÍE/(e)-E^)) = ÍE^)-E \e^—z e—'t z / \e—'t s e<—s /(e) etr Hliněný, Fl MU Brr Fl: MA010: Network Flo 6.2 Finding the maximum flow value There exist quite simple and fast algorithms to determine the maximum flow value in a given network. Problem 6.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 \\f\\ is maximized (among all admissible flows in S), c Is the depicted flow really maximum possible? etr Hliněný, Fl MU Br Fl: MAOIO: Network Flo And what about this flow of value 6? The main question is; how can we certify that no better flow exists in SI 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! etr Hliněný, Fl MU Br Fl: MAOIO: Network Flo Definition 6.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. a 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|| = J2eeC w(e).n Theorem 6.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. Remark: Theorem 6.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 constrain, a cut of the corresponding size. etr Hlinený, Fl MU Br Fl: MAOIO: Network Flo Definition: Consider a flow network S and a flow / in it. A residual z-s path (in S w.r.t. /) is an undirected path in G from the source z to the sink s, i.e. a sequence of adjacent edges ei, e2,..., em, such that /(ej) < w(ej) if ej is directed from z, and /(ej) > 0 if ej is directed from s. c The quantity w(ej) — /(ej), or /(ej), respectively, is called the residual capacity of the edge ej. A residual path is that of strictly positive residual capacities. . . ^3/4 1/2 1/1 2/3 2/4^ (z)----->—•-------> « <-------•—'S--------•--------H«) residual capacities: +1 +1 +1 +2 +2 etr Hliněný, Fl MU Brno 8 Fl: MA010: Network Flo Algorithm 6.6. Ford-Fulkerson's for network flows. input < 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 ( sGU ) { 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. -*etr Hlinený, hl MU Brr Fl: MAOIO: Network Flo Proof of Algorithm 6.6: 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) /(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 /(e) - E /(e) = E /(e) = Ew(e) = ii^ii • e^U e^U e*-U eEC That is nice, and it remains to argue that ||C|| = J2e^u /(e) — J2e^u /(e) = ||/||, finishing the proof. D etr Hlinený, Fl MU Bri MAOIO: Network Flows The proof of Algorithm 6.6 shows several interesting things: Fact: If we can prove that Algorithm 6.6 stops, we prove also Theorem 6.5.c Fact: If the edge capacities in S are integral, then Algorithm 6.6 always stops. Corollary 6.7. If the edge capacities in S are integral, then Algorithm 6.6 outputs an integral flow. Improved flow algorithms Generally, one cannot guarantee that Algorithm 6.6 stops, since counterexamples exist with real capacities, but we can do better as follows, c Algorithm 6.8. Edmonds-Karp's for network flows. As in Algorithm 6.6, 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). etr Hliněný, Fl MU Brno 11 Fl: MAOIO: Network Flows r Even better, we can use the following "clever" algorithms. Algorithm 6.9. Dinitz's for network flows (a sketch), l/l/e modify Algorithm 6.6 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)\). Algorithm 6.10. MPM "Three Indians" (a sketch) Same as Algorithm 6.9, except that a layered network is saturated faster, and the total computing time is 0(\V(G)\3). etr Hliněný, Fl MU Brno 12 Fl: MAOIO: Network Flows 6.3 Generalized network flow settings Among the many ways flow networks can be generalized, we briefly mention three which are interesting and often used. 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. etr Hlinený, Fl MU Bri MAOIO: 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) —> Rq giving the lower edge capacities. A flow / is admissible in such a network if i(e) < /(e) < w(e) for every edge e of the network. uNotice that an admissible flow may not exist in such a lower-capacitated network, c Algorithm 6.11. 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 14 Fl: MAOIO: Network Flows J r 6.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 6.12. 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 6.6, and form the resulting matching M by those edges of G having nonzero flow at the end. Proof of Algorithm 6.12: By Corollary 6.7, 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. D 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 6.13. 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. c This statement immediately implies Theorem 2.6 (Menger's)! etr Hliněný, Fl MU Brno 16 Fl: MAOIO: Network Flows r Systems of distinct representatives (SDR) Definition: Let Mi, M2, • • •, Mj. be a collection of nonempty sets. A system of distinct representatives (SDR) of the set family {Mi,M2,... ,Mj.} is a sequence of pairwise distinct elements (xi, X2,..., Xk) such that Xj G Mi for i = 1, 2,..., k. c Theorem 6.14. (Hall) Let {Mi, M2,..., M^} 6e a family of nonempty sets. Then there exists a system of its distinct representatives if, and only if, VJc{l,2,...,fc}:|U 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. etr Hliněný, Fl MU Brno 17 Fl: MAOIO: Network Flows