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.