Applications of Flows and Cuts
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
- A bipartite matching of size K is exactly an integral source-to-sink flow of value K when middle edges and endpoint-capacity edges all have capacity 1.
- Minimum bipartite vertex cover can be found by a minimum cut with infinite-capacity middle edges; finite cut edges correspond directly to selected cover vertices.
- In project selection, infinite-capacity dependency edges enforce closure, and maximum profit is total positive profit minus the minimum-cut value.
- Baseball elimination is a feasibility test: a full flow assigns every remaining game’s win while respecting each rival’s maximum allowable wins.
- A cycle cover becomes a perfect matching after splitting each vertex into an out-copy and an in-copy, with original directed edges connecting the corresponding copies.
- Orienting edges with maximum in-degree H is equivalent to assigning each edge to one endpoint under capacity H; feasibility is monotone, so binary search finds the minimum H.
Chapters
- Kent Quanrud frames the lecture as a survey of applications building on earlier flow and cut material.
- The examples range from disjoint paths and matching to project planning, playoff elimination, and graph density.
- The recurring task is to change the input representation so a flow or cut algorithm can solve the original problem.
- A matching selects as many bipartite edges as possible without sharing endpoints.
- The example graph yields a matching of 5 edges, though the initial greedy selection is not established as optimal.
- The same capacity-one idea applies to vertex-disjoint paths by limiting flow through each vertex.
- A vertex cover chooses the fewest vertices while including at least one endpoint of every edge.
- The sample graph has a cover of size 5, compared with the easy upper bound of 6 from selecting one full side.
- The problem is later converted into a minimum cut rather than a maximum-flow objective.
- Each project has a positive profit or negative cost, and selecting a project requires selecting all downstream dependencies.
- The sample includes profits of $4, $6, and $2, plus costs of $2, $3, and $5.
- Selecting the $4, $6, and $2 projects with their required dependencies produces a net profit of $2 in the class example.
- The question is whether Boston can still tie for first if it wins all of its remaining games.
- Remaining games between New York, Baltimore, and Toronto constrain which teams can receive wins.
- In the example, assigning wins to keep New York below 93 still leaves a final game that forces one rival to 93, eliminating Boston.
- A qualification matrix represents which of several people can fill each job, with the goal of assigning as many people as possible.
- A cycle cover selects vertex-disjoint cycles that cover every vertex; the illustrated cover contains cycles of lengths 5 and 3.
- Edge orientation seeks to minimize maximum in-degree, while densest subgraph maximizes edges divided by vertices; a 5-vertex clique has density 10/5 = 2.
- Add a source and sink, direct every bipartite edge from left to right, and give the edges capacity 1.
- Source-to-left and right-to-sink capacity-one edges ensure each endpoint participates in at most one selected edge.
- An integral flow of value K corresponds to a matching of size K, and each matching yields such a flow.
- Use the directed source-left-right-sink matching network, but give every middle edge infinite capacity.
- A finite cut can then select only source-side or sink-side edges, which correspond to choosing vertices in the cover.
- Every left-to-right path represents an original edge, so cutting at least one end of every path gives a vertex cover; conversely, a cover defines a cut of the same size.
- Connect the source to each positive-profit project with capacity equal to its profit, and connect each cost project to the sink with capacity equal to its absolute cost.
- Represent project dependencies with infinite-capacity directed edges so a finite cut cannot select a project while excluding a required dependency.
- For a source-side project set, the cut pays for omitted positive profits and selected costs; maximum profit equals total positive profit minus the minimum-cut value.
- Adding the same constant to every project is not valid because it biases plans according to how many projects they contain.
- Create a node for each remaining game and connect the source to it with capacity 1, representing one win to assign.
- Connect each game node to the teams playing that game, then connect each team to the sink with its remaining allowable wins.
- Boston is viable if the maximum flow routes one unit for every game; the example requires flow value 5 to allocate all five wins.
- A full flow specifies game winners, while any feasible playoff outcome can be converted back into a flow of the same value.
- For job assignment, connect job and person nodes when the person is qualified, then use unit capacities to enforce one person per job and one job per person.
- An integral flow of value 10 represents 10 valid assignments in the illustrated matching formulation.
- For cycle cover, split each graph vertex into an out-copy and an in-copy, and map each directed edge a→b to an edge from a-out to b-in.
- A perfect matching in the split graph selects exactly one outgoing and one incoming edge per original vertex, forming vertex-disjoint cycles that cover the graph.
- To test a target maximum in-degree H, create a node for every original edge and a node for every original vertex.
- Connect the source to each edge-node with capacity 1, connect it to its two endpoint-nodes with infinite capacity, and give each vertex-to-sink edge capacity H.
- Routing one unit for every edge assigns each edge to one endpoint, which defines an orientation with in-degree at most H.
- Binary search over H finds the smallest feasible maximum in-degree.
- The auxiliary network for orientation tests whether every edge can be assigned to an endpoint with capacity H.
- A subgraph with more than H edges per vertex cannot have all its edge-units routed within those vertex capacities, making it an obstruction to an H-bound orientation.
- A minimum cut identifies the relevant vertex and edge sets; their edge-to-vertex ratio exposes a dense subgraph.
- Quanrud notes that the final density argument needs careful arithmetic and points students to the course notes for the full proof.
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.