A streaming service sends video from a data centre \(s\) to an internet exchange \(t\) through four intermediate routers. Each link has a capacity in gigabits per second. Engineers route traffic along one path after another until every path they can see has a full link, and reach a total of \(8\) . Is \(8\) the most the network can carry? It is not; the network carries \(9\) . But to get there, some traffic already routed has to be taken off a link and sent another way, and a procedure that only ever adds traffic will never find the improvement.
Two questions drive this chapter. How should an algorithm revise its earlier choices so that it cannot get stuck below the optimum? And when it stops, what short proof can it offer that no better routing exists? The answers are the residual network and the minimum cut. The chapter ends with a fact that will be explained from a different direction in Chapter 6: when the capacities are whole numbers, the best routing can be chosen in whole numbers, although nothing in the problem asks for that.
3.1 Flows, cuts, and the easy inequality
Definition 3.1 (flow and its value). Let \(G=(V,A)\) be a directed graph with capacities \(u_{vw}\ge 0\) and two distinct nodes, a source \(s\) and a sink \(t\) . An \(s\) –\(t\) flow is a vector \(x\) indexed by the arcs with \(0\le x_{vw}\le u_{vw}\) for every arc and with flow conservation at every node other than \(s\) and \(t\) : the total flow on arcs entering the node equals the total on arcs leaving it. The value of the flow is the net amount leaving the source,
The maximum-flow problem asks for a flow of largest value.
The maximum-flow problem is a linear program with a bounded, nonempty feasible region (the zero flow is feasible and every \(x_{vw}\) lies between \(0\) and \(u_{vw}\) ), so by the theory of linear programming in Continuous Optimization a maximum flow exists. We could stop there and call a general-purpose solver. The reason not to is that the structure of the problem yields a much faster algorithm, a combinatorial certificate, and an integrality guarantee.
Definition 3.2 (cut and its capacity). An \(s\) –\(t\) cut is a set \(S\subseteq V\) with \(s\in S\) and \(t\notin S\) . Its capacity is the total capacity \(u(\delta^+(S))\) of the arcs leaving \(S\) . Arcs entering \(S\) do not count.
Every unit of flow must leave \(S\) at some point on its way to the sink, so no flow should exceed the capacity of any cut. The proof makes the accounting exact.
Lemma 3.3 (flow across a cut). For every flow \(x\) and every cut \(S\) ,
Equality holds on the right if and only if every arc leaving \(S\) is full and every arc entering \(S\) is empty.
Proof. For each node \(v\in S\) form the quantity “flow out of \(v\) minus flow into \(v\) ”. It equals \(\operatorname{val}(x)\) for \(v=s\) and zero for every other node of \(S\) , by conservation, since \(t\notin S\) . Add these quantities over \(v\in S\) . An arc with both ends in \(S\) contributes its flow once with a plus sign, at its tail, and once with a minus sign, at its head, and cancels. An arc leaving \(S\) contributes \(+x_{vw}\) and an arc entering \(S\) contributes \(-x_{vw}\) . Hence \(\operatorname{val}(x)=x(\delta^+(S))-x(\delta^-(S))\) . The inequality follows from \(x_{vw}\le u_{vw}\) on leaving arcs and \(x_{vw}\ge 0\) on entering arcs, and it is an equality exactly when each of those bounds is tight.
Lemma 3.3 has the shape of the bound sandwich of Chapter 1: each flow is a lower bound on the maximum, each cut is an upper bound, and a flow and a cut with equal values prove each other optimal. Taking \(S=V\setminus\{t\}\) also shows that the value equals the net flow into the sink. What remains to be shown is that the two bounds always meet.
3.2 Residual networks: how to undo a decision
Given a flow, what changes are still possible? On an arc that is not full, more flow can be pushed forward. On an arc that carries flow, some can be withdrawn, and withdrawing flow from \((v,w)\) acts, for the purposes of conservation, like pushing flow from \(w\) back to \(v\) .
Definition 3.4 (residual network, augmenting path). Let \(x\) be a flow. The residual network \(G_x\) has the same nodes as \(G\) and, for each arc \((v,w)\) of \(G\) , a forward residual arc from \(v\) to \(w\) with residual capacity \(u_{vw}-x_{vw}\) if that number is positive, and a backward residual arc from \(w\) to \(v\) with residual capacity \(x_{vw}\) if that number is positive. An augmenting path is a path from \(s\) to \(t\) in \(G_x\) , and its bottleneck is the smallest residual capacity along it.
Lemma 3.5 (augmentation). Let \(P\) be an augmenting path with bottleneck \(\varepsilon>0\) . Increase \(x_{vw}\) by \(\varepsilon\) on each arc used forward by \(P\) and decrease it by \(\varepsilon\) on each arc used backward. The result is a flow of value \(\operatorname{val}(x)+\varepsilon\) .
Proof. Capacity and nonnegativity are preserved because \(\varepsilon\) is at most each residual capacity. At an internal node of \(P\) one residual arc of \(P\) enters and one leaves, and there are four cases according to whether each is forward or backward. If both are forward, inflow and outflow each rise by \(\varepsilon\) . If both are backward, each falls by \(\varepsilon\) . If \(P\) enters forward and leaves backward, the inflow rises by \(\varepsilon\) on one arc and falls by \(\varepsilon\) on another, and the outflow is unchanged; the remaining case is symmetric. So conservation is preserved. At the source the first residual arc of \(P\) either adds \(\varepsilon\) to an outgoing arc or removes \(\varepsilon\) from an incoming one, and a path leaves \(s\) only once, so the value rises by \(\varepsilon\) .
Example 3.1: Four augmentations, one of them backwards
The network of the opening has nodes \(s,a,b,c,d,t\) and capacities
Start from the zero flow and augment along the paths in the table, which lists the residual capacities of the arcs of each path in order.
| Step | Augmenting path | Residual capacities | Bottleneck | Value after |
|---|---|---|---|---|
| 1 | \(s,a,b,d,t\) | \(7,4,5,4\) | \(4\) | \(4\) |
| 2 | \(s,a,c,t\) | \(3,4,6\) | \(3\) | \(7\) |
| 3 | \(s,b,d,c,t\) | \(6,1,3,3\) | \(1\) | \(8\) |
| 4 | \(s,b,a,c,t\) | \(5,4,1,2\) | \(1\) | \(9\) |
After step 3 the flow is \(x_{sa}=7\) , \(x_{sb}=1\) , \(x_{ab}=4\) , \(x_{ac}=3\) , \(x_{bd}=5\) , \(x_{dc}=1\) , \(x_{ct}=4\) , \(x_{dt}=4\) , of value \(8\) . This is where the engineers of the opening stopped: the arc \((s,a)\) is full, and from \(b\) the only arc of the network, \((b,d)\) , is full, so no path of unused capacity leads from \(s\) to \(t\) .
The residual network sees further. From \(b\) there is a backward residual arc to \(a\) , with residual capacity \(x_{ab}=4\) , because the flow on \((a,b)\) can be withdrawn. Step 4 uses it: one unit enters \(b\) from \(s\) , one unit is taken off \((a,b)\) , and the unit that \(a\) no longer sends to \(b\) goes to \(c\) and on to \(t\) . The second residual capacity in the last row, \(4\) , is that of the backward arc. Nothing travels from \(b\) to \(a\) ; the path describes a rerouting.
The final flow is
with value \(7+2=9\) . Is it maximum? Search the residual network from \(s\) . The arc \((s,a)\) is full. The arc \((s,b)\) has residual capacity \(4\) , so \(b\) is reachable. From \(b\) the arc \((b,d)\) is full, and the backward arc to \(a\) has residual capacity \(3\) , so \(a\) is reachable. From \(a\) the arc \((a,c)\) is full. Nothing else is reachable: \(S=\{s,a,b\}\) . The arcs leaving \(S\) are \((a,c)\) and \((b,d)\) , with capacity \(4+5=9\) , and no arc enters \(S\) from outside. By Lemma 3.3 no flow exceeds \(9\) , so the flow is maximum and the cut is minimum.
3.3 The max-flow min-cut theorem
The search that ended Example 3.1 is not a lucky feature of that instance. It is the proof of the main theorem.
Theorem 3.6 (max-flow min-cut). For a flow \(x\) in a network with source \(s\) and sink \(t\) , the following are equivalent: (a) \(x\) is a maximum flow; (b) the residual network \(G_x\) contains no augmenting path; (c) \(\operatorname{val}(x)\) equals the capacity of some \(s\) –\(t\) cut. Consequently the maximum value of a flow equals the minimum capacity of a cut.
Proof. (a) implies (b): if an augmenting path existed, Lemma 3.5 would give a flow of larger value.
(b) implies (c): let \(S\) be the set of nodes reachable from \(s\) in \(G_x\) . Then \(s\in S\) , and \(t\notin S\) because there is no augmenting path, so \(S\) is a cut. Consider an arc \((v,w)\) of \(G\) leaving \(S\) . If it were not full, its forward residual arc would make \(w\) reachable; so \(x_{vw}=u_{vw}\) . Consider an arc \((w,v)\) of \(G\) entering \(S\) , with \(v\in S\) . If it carried flow, its backward residual arc from \(v\) to \(w\) would make \(w\) reachable; so \(x_{wv}=0\) . By the equality case of Lemma 3.3, \(\operatorname{val}(x)=u(\delta^+(S))\) .
(c) implies (a): by Lemma 3.3 no flow has value larger than the capacity of any cut, so a flow whose value equals the capacity of a cut is maximum.
For the last sentence, a maximum flow \(x\) exists; by (c) there is a cut of capacity \(\operatorname{val}(x)\) , and by Lemma 3.3 no cut has smaller capacity.
The theorem suggests the augmenting path algorithm of Ford and Fulkerson: start with the zero flow; while the residual network has an augmenting path, augment along it; when it has none, report the flow together with the cut formed by the nodes reachable from \(s\) . If the algorithm stops, Theorem 3.6 guarantees that its output is optimal and certified. Whether it stops, and how soon, depends on the capacities and on which paths are chosen.
Maximum flows are not unique. In Example 3.1 another choice of paths, \(s,a,c,t\) with \(4\) units, \(s,b,d,t\) with \(4\) , and \(s,b,d,c,t\) with \(1\) , reaches value \(9\) in three steps with no flow at all on \((a,b)\) . The value is the same, and so is the cut found at the end: in every maximum flow the arcs leaving a minimum cut are full.
Common mistake. Taking “the full arcs” to be the minimum cut. In the final flow of Example 3.1 the full arcs are \((s,a)\) , \((a,c)\) , \((b,d)\) , and \((d,t)\) , with total capacity \(20\) , and they are not the arcs leaving any one cut. A cut is a set of nodes; its capacity counts only arcs directed out of the set. Find the set by searching the residual network from the source, then read off the arcs.
3.4 Whole numbers, termination, and a good path rule
Theorem 3.7 (integrality of maximum flows). If every capacity is an integer, the augmenting path algorithm started from the zero flow terminates after at most \(U^\star\) augmentations, where \(U^\star\) is the maximum flow value, and the maximum flow it returns is integral: every \(x_{vw}\) is an integer.
Proof. By induction on the number of augmentations, the flow is integral at every stage. It is so at the start. If the flow is integral, every residual capacity \(u_{vw}-x_{vw}\) or \(x_{vw}\) is an integer, hence so is every bottleneck, and adding or subtracting an integer keeps the flow integral. A bottleneck is positive, so it is at least \(1\) , and each augmentation raises the value by at least \(1\) . The value cannot exceed \(U^\star\) , so there are at most \(U^\star\) augmentations, and at termination the flow is maximum by Theorem 3.6.
Integrality is what makes flows useful for combinatorial problems, where a unit of flow stands for an indivisible thing: a path, an assignment, a person. It is a statement about the existence of an integral maximum flow, not about all maximum flows; averaging the two maximum flows of Example 3.1 gives a maximum flow with \(x_{ab}=3/2\) .
The bound of \(U^\star\) augmentations is another matter. It is proportional to a number in the input, not to the input’s length.
Example 3.2: Two thousand augmentations or two
Let the nodes be \(s,a,b,t\) with \(u_{sa}=u_{sb}=u_{at}=u_{bt}=1000\) and \(u_{ab}=1\) . The maximum flow is plainly \(2000\) : send \(1000\) along \(s,a,t\) and \(1000\) along \(s,b,t\) . Two augmentations suffice.
Suppose instead the algorithm chooses \(s,a,b,t\) first. Its bottleneck is the middle arc, so one unit is sent. Now the residual network contains the backward arc from \(b\) to \(a\) , and the path \(s,b,a,t\) has bottleneck \(1\) ; augmenting along it removes the unit from \((a,b)\) . The middle arc is empty again and the path \(s,a,b,t\) is available once more. Alternating between these two paths, every augmentation adds exactly one unit, and the algorithm performs \(2000\) augmentations before stopping. Replace \(1000\) by \(10^{9}\) and each of the four large capacities gains twenty binary digits, eighty bits in all, while the running time grows a millionfold. This is pseudo-polynomial behaviour in the sense of Definition 1.5.
With irrational capacities matters are worse: there are networks on which a perverse choice of paths produces an infinite sequence of ever smaller augmentations whose values converge to a number below the maximum. With rational capacities, multiplying by a common denominator reduces to the integer case.
The remedy is a rule for choosing the path. The simplest good rule is to take an augmenting path with the fewest arcs, which breadth-first search finds in \(O(m)\) steps. In Example 3.2 that rule picks the two-arc paths and finishes in two augmentations.
Theorem 3.8 (shortest augmenting paths). If every augmentation is made along an augmenting path with the fewest possible arcs, the algorithm terminates after at most \(nm\) augmentations, for arbitrary real capacities. Its running time is \(O(nm^2)\) .
Proof. For a flow \(x\) let \(\ell_x(v)\) be the number of arcs on a shortest path from \(s\) to \(v\) in \(G_x\) , or \(\infty\) if there is none.
Distances never decrease. Let \(x'\) be obtained from \(x\) by one augmentation along a shortest path. Suppose \(\ell_{x'}(v)<\ell_x(v)\) for some node, and choose such a \(v\) with \(\ell_{x'}(v)\) as small as possible. Let \(w\) be the node before \(v\) on a shortest path to \(v\) in \(G_{x'}\) , so \(\ell_{x'}(w)=\ell_{x'}(v)-1\) and, by the choice of \(v\) , \(\ell_x(w)\le\ell_{x'}(w)\) . If the residual arc from \(w\) to \(v\) were present in \(G_x\) , then \(\ell_x(v)\le\ell_x(w)+1\le\ell_{x'}(w)+1=\ell_{x'}(v)\) , a contradiction. So it appeared because the augmentation used the opposite residual arc, from \(v\) to \(w\) . That arc lay on a shortest path in \(G_x\) , so \(\ell_x(w)=\ell_x(v)+1\) , giving \(\ell_x(v)=\ell_x(w)-1\le\ell_{x'}(w)-1=\ell_{x'}(v)-2\) , again a contradiction.
Each residual arc is a bottleneck rarely. Call a residual arc critical in an augmentation if it attains the bottleneck; it then disappears from the residual network. Suppose the residual arc from \(v\) to \(w\) is critical when the flow is \(x\) , so \(\ell_x(w)=\ell_x(v)+1\) . Before it can be critical again it must reappear, which requires a later augmentation, at some flow \(y\) , to use the opposite residual arc from \(w\) to \(v\) ; then \(\ell_y(v)=\ell_y(w)+1\ge\ell_x(w)+1=\ell_x(v)+2\) . So between consecutive occasions on which this arc is critical, the distance of \(v\) rises by at least \(2\) . When the arc from \(v\) to \(w\) is critical, \(w\) lies on a path of the residual network, so \(\ell(w)\le n-1\) and therefore \(\ell(v)\le n-2\) . The distances of \(v\) on successive occasions are at least \(0,2,4,\dots\) and at most \(n-2\) , so the arc is critical at most \(\lfloor n/2\rfloor\) times. There are at most \(2m\) residual arcs and every augmentation has at least one critical arc, so there are at most \(2m\cdot n/2=nm\) augmentations. Each needs one breadth-first search and one pass along the path, \(O(m)\) steps.
The bound does not mention the capacities, so with this rule the algorithm is strongly polynomial. Faster algorithms exist and are used in practice; what matters for this book is that maximum flows and minimum cuts can be computed efficiently, so that they can serve as subroutines, as they will in Chapters 4 and 8.
3.5 What integral flows prove
Many statements in combinatorics that assert “the largest number of disjoint things equals the smallest number of blocking things” are the max-flow min-cut theorem with unit capacities. Two paths are arc-disjoint if they share no arc.
Corollary 3.9 (Menger’s theorem for arcs). In a directed graph with distinct nodes \(s\) and \(t\) , the maximum number of pairwise arc-disjoint paths from \(s\) to \(t\) equals the minimum number of arcs whose removal leaves no path from \(s\) to \(t\) .
Proof. Give every arc capacity \(1\) and let \(k\) be the maximum flow value, which by Theorem 3.6 is also the minimum cut capacity. A set of arcs whose removal destroys every path must contain an arc from each member of a family of arc-disjoint paths, so the maximum number of such paths is at most the minimum size of such a set; and removing the \(k\) arcs that leave a minimum cut destroys every path, so that minimum is at most \(k\) . It remains to find \(k\) arc-disjoint paths. By Theorem 3.7 there is an integral flow of value \(k\) , and we show that an integral flow of value \(k\) in a unit-capacity network contains \(k\) arc-disjoint paths. Argue by induction on \(k\) ; for \(k=0\) there is nothing to prove. If \(k\ge 1\) , start at \(s\) and walk along arcs carrying one unit of flow, never using an arc twice. Whenever the walk enters a node other than \(t\) on an unused arc, an unused arc carrying flow leaves that node: at an internal node inflow equals outflow, and at \(s\) the outflow exceeds the inflow. The walk is finite, so it ends, and it can end only at \(t\) . Deleting any cycles from it leaves a path \(P\) from \(s\) to \(t\) on arcs of flow one. Setting the flow to zero on the arcs of \(P\) leaves an integral flow of value \(k-1\) , to which the induction hypothesis applies; its paths avoid the arcs of \(P\) .
The same device, a unit of flow standing for one choice, turns assignment questions into flow questions, and then the cut explains failure.
Example 3.3: Why one student has no project
Four students must each be given one of three projects. Project \(A\) can take two students; projects \(B\) and \(C\) can take one each. Student 1 will accept \(A\) or \(B\) ; student 2 will accept \(B\) or \(C\) ; student 3 will accept only \(B\) ; student 4 will accept \(B\) or \(C\) .
Build a network with an arc of capacity \(1\) from \(s\) to each student, an arc of capacity \(1\) from each student to each project that student accepts, and an arc from each project to \(t\) with the project’s capacity: \(2\) , \(1\) , \(1\) . An integral flow of value \(4\) is an assignment of all four students, and by Theorem 3.7 the maximum flow can be taken integral, so the question is whether the maximum flow is \(4\) .
Augment along \(s,1,A,t\) , then \(s,2,B,t\) , then \(s,4,C,t\) . The value is \(3\) . Now search the residual network from \(s\) : student 3 is reachable, since the arc from \(s\) to 3 is unused. From 3 we reach \(B\) . The arc from \(B\) to \(t\) is full, but the backward arc from \(B\) to student 2 is available, and from 2 we reach \(C\) , whose arc to \(t\) is full; from \(C\) the backward arc reaches student 4, who offers nothing new. The reachable set is \(S=\{s,2,3,4,B,C\}\) . The arcs leaving it are the arc from \(s\) to student 1 and the arcs from \(B\) and \(C\) to \(t\) , of capacity \(1+1+1=3\) . So the maximum flow is \(3\) and one student must go without.
The cut says why in plain terms: students 2, 3, and 4 between them accept only projects \(B\) and \(C\) , which have two places. No rearrangement can help, and the cut is a proof of that which any of the students can check.
Because a minimum cut identifies the binding bottleneck, it also says where added capacity helps.
Example 3.4: Which link to upgrade
Return to the network of Example 3.1, whose maximum flow is \(9\) and whose minimum cut \(S=\{s,a,b\}\) has leaving arcs \((a,c)\) and \((b,d)\) . Listing all sixteen cuts shows that this one is the unique minimum; the next smallest is \(S=\{s,a,b,c,d\}\) , with leaving arcs \((c,t)\) and \((d,t)\) and capacity \(6+4=10\) .
Raising the capacity of any arc that does not leave the minimum cut, say \((s,a)\) from \(7\) to \(8\) , changes no cut of capacity \(9\) , so the maximum flow stays \(9\) . Raising \(u_{ac}\) from \(4\) to \(5\) raises the capacity of the minimum cut to \(10\) and of no other cut below \(10\) , so the maximum flow becomes \(10\) . Raising \(u_{ac}\) further, to \(6\) , achieves nothing more: the cut around the sink, with capacity \(10\) , is now the bottleneck. Upgrading one of the six arcs outside the minimum cut is wasted money; upgrading \((a,c)\) or \((b,d)\) by one unit pays off, and by more than one unit does not, until the links into \(t\) are upgraded too.
Finally, the theorem has a reading in terms of linear programming that points ahead. The maximum-flow problem is a linear program, and its dual can be shown to be a relaxation of the minimum-cut problem, in which each node receives a number between \(0\) and \(1\) in place of a definite side of the cut. Strong duality says the two linear programs have equal values; the max-flow min-cut theorem says more, namely that the dual has an optimal solution in which every node is assigned \(0\) or \(1\) , and Theorem 3.7 says the primal has an integral optimum when the capacities are integers. Both linear programs solve their integer versions. Chapter 6 identifies the property of the constraint matrix responsible for this.
Exercises
-
In the network with capacities \(u_{sa}=5\) , \(u_{sb}=4\) , \(u_{ab}=2\) , \(u_{ac}=3\) , \(u_{bc}=3\) , \(u_{bt}=3\) , \(u_{ct}=5\) , find a maximum flow by augmenting paths, listing each path with its bottleneck, and find a minimum cut by searching the final residual network.
Solution
Start from the zero flow. One possible sequence of augmenting paths, with residual capacities along each:
Step Path Residual capacities Bottleneck Value after 1 \(s,b,t\) \(4,3\) \(3\) \(3\) 2 \(s,a,c,t\) \(5,3,5\) \(3\) \(6\) 3 \(s,b,c,t\) \(1,3,2\) \(1\) \(7\) 4 \(s,a,b,c,t\) \(2,2,2,1\) \(1\) \(8\) The final flow is \(x_{sa}=4\) , \(x_{sb}=4\) , \(x_{ab}=1\) , \(x_{ac}=3\) , \(x_{bc}=2\) , \(x_{bt}=3\) , \(x_{ct}=5\) . Conservation: \(a\) receives \(4\) and sends \(1+3\) ; \(b\) receives \(4+1\) and sends \(2+3\) ; \(c\) receives \(3+2\) and sends \(5\) .
Search the residual network from \(s\) . The arc \((s,a)\) has residual capacity \(1\) , so \(a\) is reachable; \((a,b)\) has residual capacity \(1\) , so \(b\) is; \((b,c)\) has residual capacity \(1\) , so \(c\) is. The arcs \((b,t)\) and \((c,t)\) are full, so \(t\) is not reachable. The cut is \(S=\{s,a,b,c\}\) , with leaving arcs \((b,t)\) and \((c,t)\) of capacity \(3+5=8\) . The flow has value \(8\) and the cut has capacity \(8\) , so both are optimal by Lemma 3.3. A different order of paths gives a different maximum flow, but the same value.
-
For the flow \(x_{sa}=7\) , \(x_{sb}=1\) , \(x_{ab}=4\) , \(x_{ac}=3\) , \(x_{bd}=5\) , \(x_{dc}=1\) , \(x_{ct}=4\) , \(x_{dt}=4\) of Example 3.1, verify Lemma 3.3 by computing \(x(\delta^+(S))-x(\delta^-(S))\) and \(u(\delta^+(S))\) for each of the cuts \(S=\{s\}\) , \(S=\{s,a,b\}\) , and \(S=\{s,b,d\}\) .
Solution
The flow has value \(x_{sa}+x_{sb}=7+1=8\) .
Cut \(S=\{s\}\) . Leaving arcs \((s,a)\) and \((s,b)\) carry \(7+1=8\) ; no arc enters. So \(x(\delta^+(S))-x(\delta^-(S))=8\) , and \(u(\delta^+(S))=7+6=13\) .
Cut \(S=\{s,a,b\}\) . Leaving arcs \((a,c)\) and \((b,d)\) carry \(3+5=8\) ; no arc enters. The difference is \(8\) , and \(u(\delta^+(S))=4+5=9\) .
Cut \(S=\{s,b,d\}\) . Leaving arcs are \((s,a)\) , \((d,c)\) , and \((d,t)\) , carrying \(7+1+4=12\) . The arc \((a,b)\) enters \(S\) , carrying \(4\) . The difference is \(12-4=8\) , and \(u(\delta^+(S))=7+3+4=14\) .
In all three cases the net flow across the cut equals the value \(8\) , as the lemma asserts, and the capacity is an upper bound. The third cut shows why the entering arcs must be subtracted: counting only the leaving flow would give \(12\) , more than the flow’s value. The bound from the second cut, \(9\) , is the tightest of the three and is not attained by this flow because the leaving arc \((a,c)\) is not full.
-
Prove that if every capacity in a network is an even integer then the maximum flow value is even, and give an example of a network with even capacities and a maximum flow in which some arcs carry an odd amount.
Solution
Write each capacity as \(u_{vw}=2u'_{vw}\) with \(u'_{vw}\) an integer. A vector \(x\) is a flow for the capacities \(u\) exactly when \(x/2\) is a flow for the capacities \(u'\) , since halving preserves conservation and turns \(0\le x_{vw}\le u_{vw}\) into \(0\le x_{vw}/2\le u'_{vw}\) ; and the value of \(x/2\) is half the value of \(x\) . So the maximum flow value for \(u\) is twice the maximum flow value for \(u'\) . By Theorem 3.7 the latter is the value of an integral flow, hence an integer. Twice an integer is even.
For the example, let \(u_{sa}=u_{ab}=u_{ac}=u_{bt}=u_{ct}=2\) . The cut \(\{s\}\) has capacity \(2\) , so the maximum flow value is \(2\) . The flow with \(x_{sa}=2\) and \(x_{ab}=x_{ac}=x_{bt}=x_{ct}=1\) is feasible and has value \(2\) , so it is maximum, and four of its arcs carry the odd amount \(1\) . The theorem promises an integral maximum flow with a particular structure only in the sense that one exists; here the flow sending both units through \(b\) is the “even” one, and the split flow is equally optimal.
-
A network has several sources \(s_1,\dots,s_p\) and several sinks \(t_1,\dots,t_q\) , and the goal is to maximize the total flow from sources to sinks. Reduce this to a problem with one source and one sink, and explain why the reduction preserves integrality.
Hint
Add a new source \(s\) with an arc to each \(s_i\) and a new sink \(t\) with an arc from each \(t_j\) . Give the new arcs a capacity large enough never to bind, for instance the total capacity of the arcs leaving \(s_i\) or entering \(t_j\) . That number is an integer when the data are, so Theorem 3.7 applies to the enlarged network.
-
Each node \(v\) other than \(s\) and \(t\) has a limit \(g_v\) on the total flow passing through it. Show how to model node limits by splitting each node into two joined by one arc, and apply your construction to state a version of Corollary 3.9 for paths that share no internal node.
Hint
Replace \(v\) by \(v^{\text{in}}\) and \(v^{\text{out}}\) joined by an arc of capacity \(g_v\) ; arcs that entered \(v\) now enter \(v^{\text{in}}\) and arcs that left \(v\) now leave \(v^{\text{out}}\) . With every arc capacity \(1\) and every \(g_v=1\) , integral flows are families of paths sharing no internal node, and a minimum cut may be taken to consist of split arcs, that is, of nodes: the maximum number of internally node-disjoint paths from \(s\) to \(t\) equals the minimum number of nodes, other than \(s\) and \(t\) , whose removal separates them, provided \((s,t)\) is not an arc.
-
Let \(S\) and \(T\) both be minimum \(s\) –\(t\) cuts. Prove that \(S\cap T\) and \(S\cup T\) are also minimum cuts, by applying the equality case of Lemma 3.3 to a fixed maximum flow.
Solution
Fix a maximum flow \(x\) . Since \(S\) is a minimum cut, \(\operatorname{val}(x)=u(\delta^+(S))\) by Theorem 3.6, so by the equality case of Lemma 3.3 every arc leaving \(S\) is full and every arc entering \(S\) is empty. The same holds for \(T\) .
Consider \(S\cap T\) , which contains \(s\) and not \(t\) . Let \((v,w)\) leave \(S\cap T\) : then \(v\in S\cap T\) and \(w\notin S\cap T\) , so \(w\notin S\) or \(w\notin T\) . In the first case the arc leaves \(S\) , in the second it leaves \(T\) ; either way it is full. Let \((w,v)\) enter \(S\cap T\) : then \(v\in S\cap T\) and \(w\) lies outside \(S\) or outside \(T\) , so the arc enters \(S\) or enters \(T\) and is empty. By the equality case of Lemma 3.3 applied to \(S\cap T\) , \(u(\delta^+(S\cap T))=\operatorname{val}(x)\) , so \(S\cap T\) is a minimum cut.
For \(S\cup T\) : an arc \((v,w)\) leaving it has \(v\) in \(S\) or in \(T\) and \(w\) in neither, so it leaves \(S\) or leaves \(T\) and is full. An arc entering it has its head in \(S\) or in \(T\) and its tail in neither, so it enters \(S\) or \(T\) and is empty. The same lemma gives \(u(\delta^+(S\cup T))=\operatorname{val}(x)\) . A consequence is that there is a smallest minimum cut, the one found by searching the residual network from \(s\) .
-
Explain what is wrong with this claim and correct it: “In a maximum flow every arc leaving the source is full, since otherwise more flow could be sent.”
Answer
The claim is false: an arc leaving the source need not be full, because the bottleneck may lie deeper in the network. In the maximum flow of Example 3.1 the arc \((s,b)\) carries \(2\) of \(6\) . What is true is that every arc leaving a minimum cut is full, and the set \(\{s\}\) is a minimum cut only in some networks. “More flow could be sent” requires an augmenting path all the way to \(t\) , not just spare capacity at the first arc.
-
Run the augmenting path algorithm on Example 3.1 with the shortest-path rule, breaking ties in favour of the path whose second node is \(a\) ; list the augmentations, and compare the final flow and the final cut with those found in the example.
Solution
In the residual network of the zero flow the paths with fewest arcs have three arcs: \(s,a,c,t\) and \(s,b,d,t\) . The tie-break selects \(s,a,c,t\) , with residual capacities \(7,4,6\) and bottleneck \(4\) . Now \((a,c)\) is full, and the only three-arc path left is \(s,b,d,t\) , with residual capacities \(6,5,4\) and bottleneck \(4\) . The value is \(8\) .
No three-arc path remains, since \((a,c)\) and \((d,t)\) are full. The four-arc candidates are \(s,b,d,c,t\) , with residual capacities \(2,1,3,2\) , and nothing else: a path through \((a,b)\) needs at least five arcs. Augment by the bottleneck \(1\) . The value is \(9\) and the flow is
\[ x_{sa}=4,\quad x_{sb}=5,\quad x_{ab}=0,\quad x_{ac}=4,\quad x_{bd}=5,\quad x_{dc}=1,\quad x_{ct}=5,\quad x_{dt}=4 . \]Searching the residual network: \((s,a)\) has residual capacity \(3\) and \((s,b)\) has \(1\) , so \(a\) and \(b\) are reachable; \((a,c)\) and \((b,d)\) are full; nothing else is reachable. The cut is \(S=\{s,a,b\}\) with capacity \(9\) .
The flow differs from that of Example 3.1, which had \(x_{sa}=7\) and \(x_{ab}=3\) ; three augmentations sufficed in place of four, and no backward arc was needed. The value and the cut are the same, as they must be: the value is unique, and this network has only one minimum cut.
-
In a directed graph with arcs \((s,a)\) , \((s,b)\) , \((s,c)\) , \((a,d)\) , \((b,d)\) , \((c,d)\) , \((a,e)\) , \((d,e)\) , \((d,t)\) , \((e,t)\) , find the maximum number of arc-disjoint paths from \(s\) to \(t\) and a set of arcs of that size whose removal disconnects \(t\) from \(s\) .
Answer
Two. The paths \(s,a,e,t\) and \(s,b,d,t\) are arc-disjoint, and removing the two arcs \((d,t)\) and \((e,t)\) leaves no arc into \(t\) . Three arcs leave \(s\) , but only two enter \(t\) .
-
Five jobs must be run on three machines. Machine \(M_1\) can run two jobs and is able to run jobs 1, 2, 3; machine \(M_2\) can run two jobs and is able to run jobs 3, 4; machine \(M_3\) can run one job and is able to run jobs 4, 5. Model this as a flow problem, find an assignment of all five jobs, and state which theorem guarantees that the flow you find corresponds to an assignment.
Answer
Network: \(s\) to each job with capacity \(1\) ; job to each machine able to run it with capacity \(1\) ; \(M_1\) , \(M_2\) , \(M_3\) to \(t\) with capacities \(2\) , \(2\) , \(1\) . A flow of value \(5\) : jobs 1 and 2 on \(M_1\) , jobs 3 and 4 on \(M_2\) , job 5 on \(M_3\) . Theorem 3.7 guarantees an integral maximum flow, and an integral flow of value \(5\) sends each job’s single unit to exactly one machine.
-
In Exercise 10 machine \(M_2\) loses the ability to run job 3. Show by exhibiting a cut that no assignment of all five jobs exists, and translate the cut into a sentence about jobs and machines.
Solution
Now jobs 1, 2, and 3 can run only on \(M_1\) , which has room for two. In the flow network take
\[ S=\{s,\ \text{job }1,\ \text{job }2,\ \text{job }3,\ M_1\}. \]The arcs leaving \(S\) are the arcs from \(s\) to jobs 4 and 5, each of capacity \(1\) , and the arc from \(M_1\) to \(t\) , of capacity \(2\) . The arcs from jobs 1, 2, 3 go only to \(M_1\) , which is inside \(S\) , so they do not leave. The capacity of the cut is \(1+1+2=4\) .
By Lemma 3.3 every flow has value at most \(4\) , so no flow of value \(5\) exists and not all five jobs can be assigned. Read as a sentence: jobs 4 and 5 account for at most two assignments, and jobs 1, 2, 3 for at most two more because the only machine able to run them has two slots. A flow of value \(4\) is easy to exhibit, for example jobs 1 and 2 on \(M_1\) , job 4 on \(M_2\) , job 5 on \(M_3\) , so the maximum is exactly \(4\) and the cut is minimum.
-
An undirected network allows flow in either direction on each edge up to its capacity. Explain how to convert it to a directed network, and show that a maximum flow never needs to use both directions of one edge.
Hint
Replace each edge by two opposite arcs of the same capacity. If a flow uses both directions with amounts \(p\ge q>0\) , reduce both by \(q\) : conservation at both endpoints and the value are unchanged, and one direction becomes empty.
-
For the network of Example 3.2 with the value \(1000\) replaced by a general integer \(M\) , give the encoding length of the instance as a function of \(M\) , the number of augmentations in the worst case, and the number under the shortest-path rule, and classify each running time using Definition 1.5.
Answer
The instance consists of four copies of \(M\) and one \(1\) , so its length is \(4\langle M\rangle+1\) bits plus a constant for the graph. The alternating choice of paths makes \(2M\) augmentations, which is exponential in \(\langle M\rangle\) and polynomial in \(M\) : pseudo-polynomial. The shortest-path rule makes \(2\) augmentations whatever \(M\) is, consistent with the strongly polynomial bound of Theorem 3.8.
-
Prove directly from Lemma 3.3, without using Theorem 3.6, that if a flow \(x\) and a cut \(S\) satisfy \(\operatorname{val}(x)=u(\delta^+(S))\) then every maximum flow fills every arc leaving \(S\) .
Solution
Let \(y\) be any maximum flow. Since \(x\) is a flow, \(\operatorname{val}(y)\ge\operatorname{val}(x)=u(\delta^+(S))\) . Lemma 3.3 applied to \(y\) and the cut \(S\) gives \(\operatorname{val}(y)\le u(\delta^+(S))\) . Hence \(\operatorname{val}(y)=u(\delta^+(S))\) , so the inequality of Lemma 3.3 holds with equality for the pair \(y\) , \(S\) .
The lemma states that equality holds if and only if every arc leaving \(S\) is full and every arc entering \(S\) is empty. Therefore \(y\) fills every arc leaving \(S\) and puts no flow on any arc entering \(S\) . Since \(y\) was an arbitrary maximum flow, the arcs leaving \(S\) are full in every maximum flow.
The argument used only the two halves of Lemma 3.3. It shows that although maximum flows are not unique, they all agree on the arcs of every minimum cut, which is why the cut, and not the list of full arcs of one particular flow, identifies the bottleneck.
-
A flow of value \(8\) in the network of Example 3.1 has \(x_{sa}=4\) , \(x_{sb}=4\) , \(x_{ab}=0\) , \(x_{ac}=4\) , \(x_{bd}=4\) , \(x_{dc}=0\) , \(x_{ct}=4\) , \(x_{dt}=4\) . Draw or list its residual network, find an augmenting path, and say whether that path uses a backward arc.
Answer
Forward residual arcs: \((s,a)\) with \(3\) , \((s,b)\) with \(2\) , \((a,b)\) with \(4\) , \((b,d)\) with \(1\) , \((d,c)\) with \(3\) , \((c,t)\) with \(2\) . Backward residual arcs, each with capacity \(4\) : from \(a\) to \(s\) , \(b\) to \(s\) , \(c\) to \(a\) , \(d\) to \(b\) , \(t\) to \(c\) , \(t\) to \(d\) . The path \(s,b,d,c,t\) is augmenting with bottleneck \(1\) and uses forward arcs only; \(s,a,b,d,c,t\) is another. Backward arcs are available but not needed from this flow.
-
The capacity of the arc \((d,c)\) in Example 3.1 is reduced from \(3\) to \(0\) . Find the new maximum flow value and a minimum cut, and explain why the answer could not have been predicted from the old minimum cut alone.
Solution
With \(u_{dc}=0\) the arc \((d,c)\) is useless, so \(c\) can be fed only by \(a\) and \(d\) can send only to \(t\) . Consider the cut \(S=\{s,a,b,d\}\) . Its leaving arcs are \((a,c)\) , \((d,c)\) , and \((d,t)\) , with capacity \(4+0+4=8\) . So the maximum flow is at most \(8\) . The flow with \(4\) units on \(s,a,c,t\) and \(4\) units on \(s,b,d,t\) is feasible and has value \(8\) . Hence the new maximum is \(8\) and \(S=\{s,a,b,d\}\) is a minimum cut.
The old minimum cut \(\{s,a,b\}\) still has capacity \(9\) , because the arc \((d,c)\) does not leave it; looking only at that cut one would predict no change. The change comes from a different cut, \(\{s,a,b,d\}\) , whose capacity was \(4+3+4=11\) and dropped by \(3\) to \(8\) , overtaking the old minimum. Sensitivity information from a minimum cut is one-sided: it says which increases help, and says nothing about which decreases elsewhere will hurt.
-
Use breadth-first search levels, as in Chapter 2 with every arc of length one, to explain why the first augmenting path chosen by the shortest-path rule in Example 3.1 has three arcs, and list all augmenting paths with three arcs in the residual network of the zero flow.
Hint
With every arc of length one, breadth-first search from \(s\) puts \(a\) and \(b\) at distance \(1\) , \(c\) and \(d\) at distance \(2\) (the arc \((d,c)\) does not shorten anything), and \(t\) at distance \(3\) . A shortest path uses one node from each level, with arcs between consecutive levels only: \(s,a,c,t\) and \(s,b,d,t\) .
-
Write the maximum-flow problem for the network of Example 3.2 as a linear program in five arc variables and one variable for the value, and verify that the flow with \(1000\) units on each of the two outer paths satisfies every constraint.
Answer
Maximize \(f\) subject to \(x_{sa}+x_{sb}=f\) , \(x_{sa}=x_{ab}+x_{at}\) , \(x_{sb}+x_{ab}=x_{bt}\) , \(0\le x_{sa},x_{sb},x_{at},x_{bt}\le 1000\) , and \(0\le x_{ab}\le 1\) . The flow \(x_{sa}=x_{sb}=x_{at}=x_{bt}=1000\) , \(x_{ab}=0\) , \(f=2000\) satisfies the three equations, \(1000+1000=2000\) , \(1000=0+1000\) , \(1000+0=1000\) , and all bounds. It is optimal because \(f=x_{sa}+x_{sb}\le 2000\) .