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.
