Network Flow
Overview
Kent Quanrud connects edge-disjoint path packing and minimum cuts to fractional maximum flow, defining flow through edge capacities and vertex conservation and expressing the problem as a linear program. He develops the shortest-augmenting-path method known as Edmonds-Karp, whose nondecreasing BFS distances bound the running time by O(M²N), then applies integral flow to the N-rooks assignment problem.
Key takeaways
- For any S-T cut, flow value cannot exceed the sum of capacities crossing the cut; a matching flow and cut value certify optimality.
- Residual reverse capacity is not extra physical capacity: it represents the option to cancel previously routed flow and reroute it elsewhere.
- Edmonds-Karp avoids dependence on capacity magnitudes by augmenting along fewest-edge residual paths; nondecreasing BFS distances limit each edge to O(N) saturations and give O(M²N) runtime.
- With integral edge capacities, augmenting by each path's minimum residual capacity preserves integrality, so a maximum flow can be integral.
- The N-rooks assignment problem reduces to maximum flow: source-to-row and column-to-sink edges enforce uniqueness, while row-to-column edges encode allowed squares.
Chapters
- A packing of 10 edge-disjoint S-to-T paths implies every S-T cut contains at least 10 edges.
- Ford-Fulkerson adds reverse edges to the residual graph so later paths can undo earlier routing choices.
- When no residual S-to-T path remains, vertices reachable from S define a minimum cut that certifies the maximum path packing.
- An edge capacity specifies how many units of flow that edge can carry, extending unit-capacity edge-disjoint paths.
- Integer capacities can be viewed as duplicated edges, while rational capacities can be scaled to integers.
- Duplicating edges is mathematically useful but may make the algorithm depend on large capacity values, motivating a more efficient method.
- A flow assigns a numerical amount to every directed edge rather than selecting whole paths.
- On unit-capacity edges, flow can split, for example sending 0.5 units along each of two branches.
- The objective is to maximize total flow from source S to sink T while respecting each edge's capacity.
- Each edge flow must be nonnegative and no greater than its capacity.
- At every intermediate vertex, total incoming flow must equal total outgoing flow.
- Conservation means the net flow leaving S equals the net flow entering T, so either quantity gives the flow's value.
- The decision vector contains one flow variable for each edge.
- Capacity constraints apply edge by edge, while conservation contributes one equality for each nonterminal vertex.
- The objective maximizes net flow out of S, equivalently net flow into T; linear-program solvers handle these linear constraints and objective.
- Any path packing can be converted into a flow of equal value by assigning each edge the total amount of packed paths using it.
- Every feasible flow is bounded by the total capacity crossing any S-T cut.
- The edge-disjoint paths theorem establishes equality between maximum path packing and minimum cut, so maximum flow has that same value.
- Sending f units along an edge of capacity c leaves c − f units of forward residual capacity.
- The residual graph also gains f units of reverse capacity, representing the ability to undo some previously sent flow.
- This numerical update generalizes the reverse-edge trick from Ford-Fulkerson for edge-disjoint paths.
- Along a residual S-to-T path, augmenting by the minimum residual capacity sends as much flow as that route permits.
- With highly unequal capacities, a small bottleneck edge can repeatedly become the limiting edge and force many augmentations.
- The number of iterations can then depend on the capacity values, which is unsuitable for a strongly polynomial algorithm.
- A maximum-bottleneck path can improve some integer-capacity cases, but its runtime can still depend on numeric values.
- Edmonds-Karp instead uses breadth-first search to find an S-to-T path with the fewest edges in the residual graph.
- Each augmentation sends the path's bottleneck flow, then updates forward and reverse residual capacities.
- The key lemma says that after each shortest-path augmentation, the residual-graph distance from S to every vertex never decreases.
- BFS levels give each vertex's distance in number of edges, with S at level zero.
- This monotonicity controls how often residual edges can disappear and reappear, regardless of capacity magnitudes.
- When an edge u-to-v is saturated on a shortest path, v is one BFS level farther from S than u.
- If the edge later returns after using its reverse, the endpoint levels have switched order; nondecreasing distances force at least two levels of progress for a repeated reversal.
- With at most N finite BFS levels, each edge can be deleted at most O(N) times, giving O(MN) augmentations.
- A breadth-first search and residual update take O(M) time per augmentation, yielding O(M²N) total time.
- The proof considers a vertex V whose new BFS level is β and the predecessor U on a new shortest path, at level β − 1.
- Induction on the new levels establishes that U's old distance cannot exceed β − 1.
- Assuming V's old distance α is greater than β leads to a contradiction: the needed U-to-V residual edge would already give V a path of at most β edges.
- The contradiction proves α ≤ β, so no vertex becomes closer to S after augmentation.
- The puzzle asks whether N rooks can occupy allowed squares on an N-by-N board without sharing a row or column.
- Represent each row and each column as a vertex, with an allowed square corresponding to a possible row-to-column assignment.
- A rook represents one unit of flow matching a row to a distinct column.
- Add source S, one vertex per row, one vertex per column, and sink T.
- Give each S-to-row edge and each column-to-T edge unit capacity, ensuring each row and column is used at most once.
- Add a unit-capacity row-to-column edge for every unblocked square; blocked squares receive no edge.
- A flow of value N supplies one unit to every row and every column, identifying N nonattacking rook positions.
- Conversely, any valid placement of N rooks defines an integral flow of value N through the corresponding row-square-column paths.
- The constructed network has O(N²) edges and maximum flow at most N; the lecture notes that integral capacities yield an integral maximum flow.
Transcript excerpt
0:04 Okay. Off we go. So today, um we're going to keep kind of building on what we did last time, topic called network flow. So the high-level intro was, you know, you want to figure out if two vertices are connected in some sense. You can ask this question in many different ways. Okay, but we focused on two versions. One is um what's the maximum number of paths that I can kind of pack into the graph to go from S to T? Kind of two disjoint simultaneous connections. And then the other problem was uh how many edges do I need to delete so that S can no longer reach T? Okay, so maximum path packing on the left, minimum ST cut on the right. And there was always this kind of like
0:50 symmetry or duality between them. You know, you are kind of packing paths into edges. Like each edge, you can only take one of the paths that goes through it. And on the split side, on the flip side, to cut S from T, you needed to take at least one edge from every possible path from S to T. Okay, the incidence structures are like the exact same. An edge kind of gets packed into a path if and only if the path uh the edge cuts that that path. Okay, so it's like a thing. And so as a result, one inequality you actually get almost for free. Basically, any packing covering setup like this, something relatively straightforward would follow. Uh but the maximum number of paths you can take is always bounded above by the minimum number of edges in any cut. Right, and the argument wasn't too complicated. It's just that like, well,
1:37 if you can find 10 paths from S to T,
This is the start of the transcript. Save this video free for the whole transcript, searchable and time-coded.
In this course
Related notes
Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Kent Quanrud.