Q1 Ford Fulkerson
Consider the following network:
CSC373 Fall’20 Tutorial 4 Tuesday, Oct. 6, 2020
5 99
s
936 8
a
b
c
t
Solution to Q1
(a) The iterations are as follows.
4 5
4
7
d
(a) Compute a maximum flow in this network using the Ford-Fulkerson algorithm. For each iteration, write down the augmenting path, its bottleneck/residual capacity, and the value of the flow at the end of the iteration.
(b) Consider the cut X0 = (S = {s, b, c, d}, T = {a, t}). Identify all forward and all backward edges across X0. Compute the capacity of X0.
(c) Find a cut in the network whose capacity is equal to the value of the flow you computed in part (a). (This provides a guarantee that your flow is indeed maximum.) Use the idea outlined in the proof of correctness of the Ford-Fulkerson algorithm.
Iteration Augmenting Path
1 (s,a,t)
2 (s,a,c,t)
3 (s,b,c,t)
4 (s,d,t)
5 (s,b,d,t)
Residual Capacity 5
4
5
5 2
Value of Flow 5
9
14
19 21
The residual graph at the end of each iteration is shown in the figure below. After the fifth iteration, we are done as there are no more directed paths from s to t in the final residual graph.
1
(a) After Step 1 (b) After Step 2 (c) After Step 3
(d) After Step 4 (e) After Step 5
(b) The forward edges across X0 are (s, a), (b, a), (c, t), and (d, t). The backward edge across X0
is(a,c). ThecapacityofX0 is9+3+9+7=28.
(c) From looking at the final residual graph in the figure above, the set of vertices reachable from s are {s, a, b, c, d}. Hence, the cut ({s, a, b, c, d}, {t}) must be a minimum cut. Its capacity is 5 + 9 + 7 = 21, which matches the value of the maximum flow computed in part (a).
Q2 Graph Modifications
In this problem, we will consider what happens to the maximum flow when the flow network G is modified slightly.
(a) TRUE/FALSE: In any network G with integer edge capacities, there always exists an edge e such that increasing the capacity of e increases the maximum flow value in G.
(b) Suppose we are given a network G with n nodes, m edges, and integer edge capacities, and we are also given a flow f in G of maximum value. We now increase the capacity of a specific edge e by one. Give an O(m + n) time algorithm to find a maximum flow in the updated network.
Solution to Q2
(a) FALSE. Consider the following network.
s1v1t
The maximum flow in this network is 1, but clearly increasing the capacity of any single edge would
2
not increase the maximum flow as the capacity of the other edge would still serve as a bottleneck. (b) The algorithm operates as follows.
• Construct the residual graph Gf of flow f in the original network.
• If it already contains a forward edge for e, then f is still a maximum flow.
• If it does not, add a forward edge for e with capacity 1.
• If the updated residual graph contains a path P from s to t, then augmenting a unit flow along this path gives a new maximum flow f′, otherwise f is still a maximum flow.
The key observation is that the Ford-Fulkerson algorithm can start from any given flow and aug- ment it to a maximum flow. The only way the maximum flow can increase by increasing the capacity of a single edge e is if Gf does not have a forward edge for e, and by adding such an edge, a new s-t path is obtained. Further, since we are increasing the capacity of e by one, the added forward edge will also have capacity 1. Thus, when we find an s-t path, its bottleneck capacity will be 1. Thus, augmenting a unit flow along this path will remove the forward edge for e, and thus leave no further s-t paths in the residual graph.
The running time is linear because constructing the residual graph and then finding a path from s to t in this graph both take linear time.
3