Save this video free

Network Flow

Kent Quanrud · 1:15:55 · Watch on YouTube

Part of Purdue University Fundamental Algorithms (Fall 2026). See all 18 lectures and search them

These notes were made with YouTube Collector. Paste any YouTube link and get the same: a summary, chapters and a searchable transcript.

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

Chapters

0:00 Edge-Disjoint Paths and Minimum Cuts Certify Each Other
6:00 Capacities Generalize Paths and Create a Runtime Challenge
8:00 Model Maximum Flow as Divisible Water on Edges
11:00 Capacity Bounds and Conservation Define Feasible Flow
14:00 Write the Maximum-Flow Problem as a Linear Program
21:00 Maximum Flow Matches Path Packing and Minimum Cut
28:00 Residual Capacities Track Unused and Reversible Flow
32:00 Why Arbitrary Augmenting Paths Can Take Too Long
41:00 Choose Shortest Residual Paths for Edmonds-Karp
43:00 BFS Distances Never Decrease Across Augmentations
45:00 Bound Edge Reversals and Derive the O(M²N) Runtime
51:00 Prove Distance Monotonicity by Induction on BFS Levels
1:04:00 Convert the N-Rooks Puzzle into a Flow Problem
1:11:00 Build the Rook-Matching Network with Unit Capacities
1:14:00 Read a Full Flow as a Valid Rook Placement

Keep these chapters and the full searchable transcript in your own library.

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.

Want the full transcript?

Save this video in YouTube Collector to get its complete searchable transcript, your own AI summaries, and a library that keeps every video you collect in one place.