Augmenting flows and refinements
Studying this course? Keep your progress in one place.
Key facts
- A flow-augmenting route increases flow by its smallest spare capacity, using forward spare capacity and backward flow.
- Stop when no augmenting route exists; the nodes reachable from define a minimum cut.
- With limits on an arc with flow : forward spare is and backward amount is .
- A node with limited capacity is split into two nodes joined by an arc of that capacity.
- Raising an arc's capacity helps only if the arc is in every minimum cut.
Augmenting a flow
Find a route from to with spare capacity, and increase the flow by the smallest spare amount on it.
A flow-augmenting route goes from to . On an arc used in its own direction the spare capacity is capacity flow. An arc may also be used backwards: if arc carries flow , travelling from to can cancel up to units.
Increase the flow by the smallest spare capacity (or backward flow) along the route, the bottleneck. Then update every arc: add the amount on forward arcs, subtract it on backward arcs.
Example: arc with capacity 6 and flow 4 has forward spare capacity 2.
- Forward spare capacitycapacity flow
- Backward amountcurrent flow on the arc
- Increase along a routesmallest of these
An arc has capacity 9 and flow 5. What is the forward spare capacity, and how much can be cancelled by a backward move?
The augmenting algorithm
Keep augmenting until no route exists; the flow then equals the capacity of a cut, so it is a maximum.
Start with any feasible flow (for example zero). Repeatedly find a flow-augmenting route and increase the flow by its bottleneck. Stop when no augmenting route exists.
Then the nodes reachable from (by forward arcs with spare capacity and backward arcs with positive flow) form the set . Every arc leaving is saturated and every arc entering it carries no flow, so the flow equals the capacity of the cut . By the max-flow min-cut theorem it is maximal.
Worked example
Starting from the flow shown (value 4), find the maximum flow.
- 1
Route : spare capacity on is 2, on is 3. Add 2. Total flow 6.
- 2
Route , using backwards: spare 3, carries 4 so up to 4 can be cancelled, spare now 1. Add 1. Total flow 7.
- 3
No further route exists. The cut has capacity .
Why can you stop when no augmenting route exists?
Upper and lower capacities
With limits the flow on an arc must stay between them, so backward moves can only cancel flow down to .
Some arcs have a lower capacity as well as an upper capacity, written : the flow must satisfy .
A feasible flow meets every arc's limits and conserves flow at every intermediate node. Find one first (by trial if needed), then augment it.
Lower capacities also set a minimum flow: if and into the sink, every feasible flow has value at least 7.
- Forward spare capacity
- Backward amount
- Capacity of a cut
Worked example
An arc has limits and carries flow 5. Find the forward spare capacity and the most that a backward move can cancel.
- 1
Forward spare .
- 2
Backward amount .
An arc has limits and flow 6. What is the most flow you can cancel using it backwards?
Nodes of restricted capacity
Split the node into two joined by an arc whose capacity is the restriction.
Sometimes a node, not an arc, limits the flow, for example a depot that can handle at most 6 units per hour. This is a restricted node.
Use node splitting: replace node by and joined by an arc whose capacity is the restriction. Every arc that entered now enters , and every arc that left now leaves . The new arc is then treated like any other, and may appear in a minimum cut.
- 1
Original node B
arcs enter and leave B; total limited to 6
- 2
Split into B1 and B2
arcs into B go to B1; arcs out of B leave B2
- 3
Join B1 to B2
give this new arc the restriction, capacity 6
Worked example
Arcs 8, 7, 4, 5, 6, 5, 9. Find the maximum flow when the flow through is limited to 6.
- 1
Without the restriction the minimum cut is : , so the maximum flow is 14.
- 2
Split into and with arc of capacity 6.
- 3
The cut has arcs and : .
A node can handle at most 10 units. Where do you put the restriction?
Refining and evaluating a model
Raising an arc's capacity helps only if it lies in every minimum cut, and only until another cut becomes the minimum.
Once the maximum flow is known, the minimum cuts show where the bottleneck is.
Raising an arc's capacity increases the maximum flow only if that arc is in every minimum cut, and then the flow rises by the increase or until another cut becomes the minimum, whichever is smaller.
Example: raising a capacity by 2 may raise the maximum flow by only 1 if another cut has capacity one more than the current minimum.
Always check the next smallest cut before you give the new maximum, and state conclusions in context with units.
Arc in every minimum cut
- Raising capacity can raise the maximum flow
- Rise stops when another cut becomes the minimum
Arc not in every minimum cut
- Raising capacity leaves the maximum flow unchanged
The minimum cut has capacity 11 and the next smallest, which does not contain the arc, has capacity 12. An arc in the only minimum cut has its capacity raised by 3. What is the new maximum flow?
Try an exam question
Arc has capacity and flow . Arc has capacity and flow . Find the amount by which the route can increase the flow, and the new flow on each of the two arcs.
[4 marks]
- [1]Spare capacity on is .
- [1]Spare capacity on is .
- [1]The flow can increase by the smaller, .
- [1]New flows: 8 and 8 (arc is saturated).
That's the notes covered.
Carry on to the next subtopic.
Try a question
By how much can the flow be increased along the route ?
1 mark, marked against the mark scheme
By how much can the flow be increased along the route ?
1 mark, marked against the mark scheme