Packing and Covering Paths
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
- For any graph and vertices S and T, the maximum number of edge-disjoint S-to-T paths equals the minimum number of edges whose removal disconnects S from T.
- A residual graph adds reverse edges for previously selected paths so later augmentations can cancel earlier choices and repair a greedy packing.
- When no residual S-to-T path remains, the vertices reachable from S identify a minimum cut, and its size equals the number of augmentations.
- The augmenting-path method takes O(mλ) time, where m is the number of edges and λ is the maximum number of edge-disjoint paths.
- The minimum-cut side provides a compact co-NP certificate that fewer than K edge-disjoint paths exist: exhibit an S-T cut with at most K−1 edges.
- Vertex-disjoint path problems can be reduced to edge-disjoint path problems by splitting each vertex into in and out copies connected by a capacity edge.
Chapters
- A 1950s or 1960s USSR railroad map illustrates how removing a few edges could disrupt a transportation network.
- CPU design uses redundant, well-connected networks to tolerate imperfect components.
- Social-network paths measure degrees of separation, while web-link structure helped Google rank pages beyond keyword matching.
- Basic questions include whether S reaches T, the shortest path length, and the number of paths of bounded length.
- Counting all S-to-T paths may be difficult because a graph can contain exponentially many paths.
- Random walks offer another connectivity measure, such as the probability or expected time to reach T.
- The example graph has two edge-disjoint S-to-T paths, which limits how many paths can be packed.
- An S-T cut removes edges to disconnect S from T; every S-to-T path must contain at least one cut edge.
- Path packing and cut covering use the same path-edge incidence structure: pack as many paths as possible, or cover every path with as few edges as possible.
- For any edge-disjoint path set P and any S-T cut C, each path in P must use an edge of C.
- Because paths in P share no edges, their required cut edges are distinct, so |P| ≤ |C|.
- This establishes that the maximum number of edge-disjoint paths cannot exceed the minimum cut size.
- A natural algorithm repeatedly finds an S-to-T path and deletes its edges, taking one graph search per path.
- A poor first path can consume edges needed for a larger packing; the grid-like counterexample can make the gap arbitrarily large.
- Choosing a shortest path does not generally solve the problem, and ordinary BFS layers do not provide a reliable fix.
- After finding a path, the algorithm adds reverse versions of its edges to a residual graph instead of simply deleting the original edges.
- A later path can use a reverse edge to cancel an earlier choice, allowing the paths to be uncrossed into valid paths in the original graph.
- The reverse edges are an auxiliary mechanism for revising the packing, not new edges in the input graph.
- When no residual S-to-T path remains, the vertices still reachable from S define one side of a cut.
- For this cut, each augmentation decreases the number of forward crossing residual edges by exactly one.
- The number of augmentations therefore equals the size of the final cut, and weak duality sandwiches both quantities to equality.
- The algorithm returns both a maximum edge-disjoint path packing and a minimum S-T cut.
- If λ is the optimum number of edge-disjoint paths, the algorithm performs λ augmentations.
- Each augmentation finds a path with a graph search costing O(m), giving total time O(mλ).
- Since λ is at most the number of edges m, this bound is polynomial in the graph size.
- A yes-instance asking whether there are at least K edge-disjoint paths has an NP certificate: provide K paths and verify they share no edges.
- A no-instance has a cut certificate: a cut with at most K−1 edges proves K paths cannot exist.
- The max-path/min-cut equality supplies the cut certificate and places the decision problem in co-NP.
- Polynomial-time problems lie in both NP and co-NP, while NP-hardness is a separate claim about solving every problem in NP.
- Pratt's certificate showed that primality has a polynomially checkable proof, an important step before the AKS deterministic polynomial-time primality algorithm.
- Graph isomorphism has certificates for yes and no answers and a quasipolynomial-time algorithm, but no known polynomial-time algorithm.
- A dual optimization problem can provide efficiently checkable evidence that a proposed solution is impossible.
- Vertex-disjoint paths can be fewer than edge-disjoint paths when several routes share a bottleneck vertex.
- Split each vertex into an in-copy and an out-copy, joined by an edge that represents using that vertex.
- Apply the edge-disjoint-path algorithm to the transformed graph rather than designing a separate algorithm.
- An edge capacity such as 3 can represent three usable copies of that edge, preserving the unweighted packing interpretation for integer capacities.
- Augmenting one path at a time can take too long when capacities are very large, such as values exponential in the graph size.
- Rational capacities can be scaled to integers using a common denominator; real capacities can be approximated by rationals to recover the structural theorem within an arbitrarily small error.
- A cycle cover selects vertex-disjoint cycles that together contain every vertex.
- The example covers eight vertices with one five-cycle and one triangle, leaving other graph edges unused.
- Quanrud poses finding a cycle cover as a puzzle and notes that the preceding graph techniques can help solve it.
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.