A network has s to a of capacity 10, s to b of capacity 5, a to b of capacity 4, a to t of capacity 6 and b to t of capacity 8. Compute the maximum flow, name a minimum cut, and prove your value is optimal without running an augmenting path search to completion.

A network has s to a of capacity 10, s to b of capacity 5, a to b of capacity 4, a to t of capacity 6 and b to t of capacity 8. Compute the maximum flow, name a minimum cut, and prove your value is optimal without running an augmenting path search to completion.

Approach: Find any feasible flow of the value you claim, then exhibit a cut of the same capacity. Weak duality then closes the gap with no further search.

14. Route 6 along s, a, t and 4 along s, a, b, t, which uses all 10 units on s to a and all 4 on a to b, then route 4 along s, b, t, which brings b to t up to its capacity of 8. The flow value is 6 + 4 + 4, that is 14. The cut separating {s, a, b} from {t} has capacity 6 + 8, also 14, so weak duality bounds every feasible flow by 14 and the flow just built is therefore a maximum flow while that cut is a minimum cut. Once a flow and a cut of equal value are in hand no search of the residual graph is needed, since any flow is at most any cut. One unit of the s to b capacity is left unused at the optimum, which shows that saturating every source edge is not a requirement for optimality.

Follow-up: If you could buy one extra unit of capacity on a single edge, which edge raises the maximum flow and by how much?

Key concepts: maximum flow, minimum cut, weak duality, residual graph.