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.