CS 163/265, Winter 2026, Practice Problem Set 8

For the flow network below, for maximum flows from s to t, with the capacities shown:

A graph with four vertices s, a, b, and t. There are edges with capacities 3 from s to a, 6 from s to b, 2 from a to b, 5 from b to a, 7 from a to t, and 4 from b to t.

  1. Find the sequence of flows and residual graphs that would be found by repeatedly augmenting on unweighted shortest residual paths (the residual paths with the smallest numbers of edges). When you have a choice for which path to choose, you may choose any shortest path.

  2. Find the sequence of flows and residual graphs that would be found by repeatedly augmenting on widest residual paths (the residual paths with the largest capacity). When you have a choice for which path to choose, you may choose any widest path.

  3. This flow network has two minimum cuts. Which vertices are separated by these cuts? Which one would be found by the method for converting a maximum flow into a minimum cut described by the lecture notes (on the slide labeled "If this algorithm terminates it finds a minimum cut")?

  4. As in several other examples we have seen, this flow network includes a pair of edges that connect the same two vertices in opposite directions: one edge is directed from a to b while the other is directed from b to a. Suppose we have a network with a pair of edges like this, and a maximum flow that uses both of these edges, with flow amounts \(f_{\mathrm{ab}}\) on the edge from a to b and \(f_{\mathrm{ba}}\) on the edge from b to a. Describe how to find another maximum flow that uses at most one of these two edges, and has zero flow on the other edge.

  5. For 266 students, based on the graduate reading: The reading describes an algorithm for maximum flow, whose runtime \(O(m\eta)\) depends on a parameter \(\eta\) (the Greek letter eta). This parameter value can be calculated by combining an optimal flow with a predicted flow; the predicted flow must respect the requirement that flow in equals out at each internal vertex, but can exceed the edge capacities. What is the value of \(\eta\) on this network when the optimal flow is the result from question 1 and the predicted flow sends five units of flow on each of sb, bt, sa, and at, and does not send any flow on ab or ba?