0:00

So now I get to tell you about the very cool randomized contraction algorithm for

Â computing the minimum cut of a graph. Let's just recall what the minimum cut

Â problem is. We're given as input an undirected graph. And the parallel edges are

Â allowed. In fact, they will arise naturally throughout the course of the algorithm.

Â That is, we're given pair of vertices, which have multiple edges which have that pair

Â as endpoints. Now, I do sort of assume you've watched the other video on how

Â graphs are actually represented, although that's not going to play a major role in

Â the description of this particular algorithm. And, again, the goal is to

Â compute the cut. So, a cut is a partition of the graph vertices into two groups, A

Â and B. The number of edges crossing the cut is simply those that have one endpoint

Â on each side. And amongst all the exponentially possible cuts, we want to

Â identify one that has The fewest number of crossing edges, or a "min cut". >>So, here's

Â the random contraction algorithm. So, this algorithm was devised by David Karger back

Â when he was an early Ph.D student here at Stanford, and this was in the early 90s. So

Â like I said, quote unquote only about twenty years ago. And the basic idea is to

Â use random sampling. Now, we'd known forever, right, ever since QuickSort, that

Â random sampling could be a good idea in certain context, in particular when you're

Â sorting and searching. Now one of the things that was such a breakthrough about

Â Karger's contraction algorithm is, it showed that random sampling can be

Â extremely effective for fundamental graph problems. >>So here's how it works. We're

Â just gonna have one main loop. Each iteration of this while-Loop is going to

Â decrease the number of vertices in the graph by 1, and we're gonna terminate

Â when we get down to just two vertices remaining. Now, in a given iteration,

Â here's the random sampling: amongst all of the edges that remain in the graph to this

Â point, we're going to choose one of those edges uniformly at random. Each edge is

Â equally likely. Once you've chosen an edge, that's when we do the contraction.

Â So we take the two endpoints of the edge, call them the vertex u and the vertex v,

Â and we fuse them into a single vertex that represents both of them. This may become

Â more clear when I go through a couple examples on the next couple of slides.

Â This merging may create parallel edges, even if you didn't have them before.

Â That's okay. We're gonna leave the parallel edges. And it may create a

Â self-loop edge pointer that both of the endpoints is the same. And self-loops are

Â stupid, so we're just gonna delete as they arise. Each generation decreases the

Â number of vertices that remain. We start with N vertices. We end up with 2. So

Â after N-2 generations, that's when we stop and at that point we return the

Â cuts represented by those two final vertices. You might well be wondering what

Â I mean by the cut represented by the final two vertices. But I think that will become

Â clear in the examples, which I'll proceed to now. >>So suppose the input graph

Â is the following four node, four edge graph. There's a square plus one diagonal.

Â So, how would the contraction algorithm work on this graph? Well, of course, it's

Â a randomized algorithm so it could work in different ways. And so, we're gonna look

Â at two different trajectories. In the first iteration each of these five edges

Â is equally likely. Each is chosen for contraction with twenty percent

Â probability. For concreteness, let's say that the algorithm happens to choose this

Â edge to contract, to fuse the two endpoints. After the fusion these two

Â vertices on the left have become one, whereas the two vertices on the right are

Â still hanging around like they always were. So, the edge between the two

Â original vertices is unchanged. The contracted edge between the two vertices on the left

Â has gotten sucked up, so that's gone. And so what remains are these two edges here.

Â The edge on top, and the diagonal. And those are now parallel edges, between the

Â fused node and the upper right node. And then I also shouldn't forget the bottom

Â edge, which is edge from the lower right node to the super node. So that's what we

Â mean by taking a pair of the vertices and contracting them. The edge that was

Â previously connected with them vanishes, and then all the other edges just get

Â pulled into the fusion. >>So that's the first iteration of Karger's algorithm of

Â one possible execution. So now we proceed to the second iteration of the contraction

Â algorithm, and the same thing happens all over again. We pick an edge, uniformly at

Â random. Now there's only four edges that remain, each of which is equally likely to

Â be chosen, so the 25% probability. For concreteness, let's say that in the

Â second iteration, we wind up choosing one of the two parallel edges, say this one

Â here. So what happens? Well, now, instead of three vertices, we go down to 2. We

Â have the original bottom right vertex that hasn't participated in any contractions at

Â all, so that's as it was. And then we have the second vertex, which actually

Â represents diffusion of all of the other three vertices. So two of them were fused,

Â the leftmost vertices were fused in iteration 1. And now the upper right

Â vertex got fused into with them to create this super node representing three

Â original vertices. So, what happens to the four edges? Well, the contracted one

Â disappears. That just gets sucked into the super node, and we never see it again.

Â Again, and then the other three go, and where there's, go where they're supposed

Â to go. So there's the edge that used to be the right most edge. That has no hash

Â mark. There's the edge with two hash marks. That goes between the, the same two

Â nodes that it did before. Just the super node is now an even bigger node

Â representing three nodes. And then the edge which was parallel to the one that we

Â contracted, the other one with a hash mark becomes a self-loop. And remember what

Â the, what the algorithm does is, whenever self loops like this appear, they get

Â deleted automatically. And now that we've done our N-2 iterations, we're

Â down to just two nodes. We return the corresponding cut. By corresponding cut,

Â what I mean is, one group of the cut is the vertices that got fused into each

Â other, and wound up corresponding to the super node. In this case, everything but

Â the bottom right node, And then the other group is the original nodes corresponding

Â to the other super node of the contracted graphs, which, in this case, in just the

Â bottom right node by itself. So this Set A is going to be these three nodes here,

Â which all got fused into each other, contracted into each other. And B is going

Â to be this node over here which never participated in any contractions at all.

Â And what's cool is, you'll notice, this does, in fact, define a min cut. There are

Â two edges crossing this cut. This one, the rightmost one and the bottommost one. And

Â I'll leave it for you to check that there is no cut in this graph with fewer than

Â two crossing edges, so this is in fact a min cut. >>Of course, this is a randomized

Â algorithm, and randomized algorithms can behave differently on different

Â executions. So let's look at a second possible execution of the contraction

Â algorithm on this exact same input. Let's even suppose the first iteration goes

Â about in exactly the same way. So, in particular, this leftmost edge is gonna

Â get chosen in the first iteration. Then instead of choosing one of the two

Â parallel edges, which suppose that we choose the rightmost edge to contract in

Â the second iteration. Totally possible, 25% chance that it's gonna happen. Now

Â what happens after the contraction? Well, again, we're gonna be left with two nodes,

Â no surprise there. The contracted node gets sucked into oblivion and vanishes.

Â But the other three edges, the ones with the hash marks, all stick around, and

Â become parallel edges between these two final nodes. This, again, corresponds to a

Â cut (A, B), where A is the left two vertices, and B is the right two vertices.

Â Now, this cut you'll notice has three crossing edges, and we've already seen that

Â there is a cut with two crossing edges. Therefore, this is <i>not</i> a min cut. >>So what

Â have we learned? We've learned that, the contractual algorithm sometimes

Â identifies the min cut, and sometimes it does not. It depends on the random choices

Â that it makes. It depends on which edges it chooses to randomly contract. So the

Â obvious question is, you know, is this a useful algorithm. So in particular, what

Â is the probability that it gets the right answer? We know it's bigger than 0, and

Â we know it's less than 1. Is it close to 1, or is it close to 0? So we find

Â ourselves in a familiar position. We have what seems like a quite sweet

Â algorithm, this random contraction algorithm. And we don't really know if

Â it's good or not. We don't really know how often it works, and we're going to need to

Â do a little bit of math to answer that question. So in particular, we'll need

Â some conditional probability. So for those of you, who need a refresher, go to your

Â favorite source, or you can watch the Probability Review Part II, to get a

Â refresher on conditional probability and independence. Once you have that in your

Â mathematical toolbox, we'll be able to totally nail this question. Get a very

Â precise answer to exactly how frequently the contraction algorithm successfully

Â computes the minimum cut.

Â