Save this video free

Packing and Covering Paths

Kent Quanrud · 1:08:13 · 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 develops the connection between packing edge-disjoint S-to-T paths and covering them with an S-T cut: the maximum number of edge-disjoint paths equals the minimum number of cut edges. He explains how augmenting paths in a residual graph undo poor greedy choices, prove the equality, and compute both optima in O(mλ) time, then connects the cut certificate to co-NP and extends the discussion to vertex-disjoint paths, capacities, and cycle covers.

Key takeaways

Chapters

0:00 Connectivity in Railroads, CPUs, Social Networks, and the Web
4:20 Ways to Measure Connectivity Between S and T
6:20 Edge-Disjoint Paths and S-T Cuts as Packing and Covering
13:00 Weak Duality: Every Path Packing Is Bounded by Every Cut
16:00 Why Greedy Path Removal Can Miss the Maximum
25:30 Residual Edges Let Augmenting Paths Undo Bad Choices
33:00 Residual-Cut Counting Proves Max-Flow Min-Cut for Paths
42:20 The Augmenting-Path Algorithm Runs in O(mλ) Time
45:00 Path Packing Has Both NP and co-NP Certificates
50:00 Duality, co-NP, Primality, and Graph Isomorphism
56:40 Convert Vertex-Disjoint Paths into Edge-Disjoint Paths
1:00:05 Capacities Extend Path Packing but Complicate Runtime
1:04:55 Cycle Covers as the Closing Graph Puzzle

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

Transcript excerpt

0:06 Let's uh let's start. Okay, so today uh we're doing a topic called uh packing and covering paths. Okay, this is going to be another graph heavy class. Hopefully that's more fun. Um but [snorts] it's gonna it's going to focus on this like highle question of I give you like a graph and like two vertices and at a high level how well are S&T connected? Okay. And this is a a very natural question uh to ask. Uh for example, I found this in Jeff's notes. Uh, this is I guess a map of like USSR railroads in like 1950s, 1960s or something. It's probably dated somewhere.

0:54 Maybe it's not. Um, but they were looking at this map and they said, "Look, if we had to drop a a couple missiles to disrupt some hit some railroads, what would be the most disruptive points?" Right? If you could just take out two of these legs or something, how would that disrupt their whatever they do the most? Okay. Uh that's so that you know how well you can disrupt something and then on the dual side you know kind of I guess Russia is probably wondering like how robust is our network? How well connected are things even if a few things fail. Um a similar question of course uh comes up in CPUs. So CPUs are like amazing right because uh they're not perfect right? So they're they're so small uh and they're done at such a small

1:40 scale that they can't make perfect CPUs. In fact, this is like a big breakthrough in the 20th century to realize you don't have to make perfect CPUs uh if they can just correct themselves and things like this. So there's a lot of redundancy built in in CPU design at the very low

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.