Save this video free

Applications of Flows and Cuts

Kent Quanrud · 1:08:36 · 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 shows how to model diverse optimization problems as maximum-flow or minimum-cut instances, including bipartite matching, minimum vertex cover, project selection, baseball elimination, job assignment, cycle cover, edge orientation, and densest subgraph. The central techniques are to represent choices as integral flow, encode constraints with capacities, and prove both directions of each reduction; minimum cuts also capture minimum-cost or maximum-profit solutions.

Key takeaways

Chapters

0:00 Flows and Cuts as a Toolkit for Optimization Problems
1:24 Bipartite Matching and Vertex-Disjoint Choices
3:24 Minimum Vertex Cover in a Bipartite Graph
4:45 Project Planning with Profits, Costs, and Dependencies
6:32 Baseball Playoff Elimination by Allocating Remaining Wins
9:52 Applications Survey: Job Assignment, Cycle Cover, and Density
15:20 Maximum Bipartite Matching as an Integral Flow
19:03 Minimum Bipartite Vertex Cover as a Minimum Cut
25:52 Project Selection as a Minimum-Cut Profit Calculation
39:10 Baseball Elimination as a Game-to-Team Flow Assignment
47:06 Job Assignment and Cycle Cover as Matching Problems
53:48 Edge Orientation as Assigning Edges to Endpoints
1:00:43 Densest Subgraph and the Orientation Feasibility Cut

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

Transcript excerpt

0:05 All right. Today is the third of three lectures on flows and cuts. It's also the last uh lecture obviously before the midterm, but this material will basically still be on the midterm. It's a continuation of last week, so it's not like it's not like when we did SAT right before the midterm. So hopefully it'll it'll kind of count as practice. Um we do know that like you haven't you've done maybe one flow homework problem for homework, but not like a lot. So if we do have a flow word problem, it's usually on the milder end. But I mean that's a little subjective, but in general we keep that in mind. Okay, so all right. So um flows and cuts are actually really fun uh because they can solve like a gazillion things and some of them are a little bit surprising. Okay. So I'm just going to basically uh start by introducing like seven different problems or something

0:53 just sweeping through uh so you can see the problem, get used to the rules, and then we'll go back one by one and see how many we can solve together um as time permits. So it's just a problem solving class. Uh but um okay. So let me go through one by one. Uh ah almost everything today is going to be under change the input uh thing uh as you might have expected. Okay. Yeah, so I'm going to survey a bunch of problems. Go one by one starting with uh we've already kind of done this, but I'll just leave it up here. Go through it really quickly. Um we did edge disjoint paths or edge capacity flow in the last two classes. Uh but of course you can do vertex disjoint paths, vertex

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.