1
00:00:00,000 --> 00:00:04,257
So now I get to tell you about the very
cool randomized contraction algorithm for

2
00:00:04,257 --> 00:00:07,357
computing the minimum cut of a graph.
Let's just recall what the minimum cut

3
00:00:07,357 --> 00:00:12,013
problem is. We're given as input an
undirected graph. And the parallel edges are

4
00:00:12,013 --> 00:00:15,548
allowed. In fact, they will arise naturally
throughout the course of the algorithm.

5
00:00:15,548 --> 00:00:19,084
That is, we're given pair of vertices, which
have multiple edges which have that pair

6
00:00:19,084 --> 00:00:23,123
as endpoints. Now, I do sort of assume
you've watched the other video on how

7
00:00:23,123 --> 00:00:26,951
graphs are actually represented, although
that's not going to play a major role in

8
00:00:26,951 --> 00:00:29,757
the description of this particular
algorithm. And, again, the goal is to

9
00:00:29,757 --> 00:00:33,831
compute the cut. So, a cut is a partition
of the graph vertices into two groups, A

10
00:00:33,831 --> 00:00:37,781
and B. The number of edges crossing the
cut is simply those that have one endpoint

11
00:00:37,781 --> 00:00:41,143
on each side. And amongst all the
exponentially possible cuts, we want to

12
00:00:41,143 --> 00:00:46,722
identify one that has The fewest number of
crossing edges, or a "min cut". >>So, here's

13
00:00:46,722 --> 00:00:52,258
the random contraction algorithm. So, this
algorithm was devised by David Karger back

14
00:00:52,258 --> 00:00:55,954
when he was an early Ph.D student here at
Stanford, and this was in the early 90s. So

15
00:00:55,954 --> 00:01:00,163
like I said, quote unquote only about
twenty years ago. And the basic idea is to

16
00:01:00,163 --> 00:01:03,833
use random sampling. Now, we'd known
forever, right, ever since QuickSort, that

17
00:01:03,833 --> 00:01:07,845
random sampling could be a good idea in
certain context, in particular when you're

18
00:01:07,845 --> 00:01:10,542
sorting and searching. Now one of the
things that was such a breakthrough about

19
00:01:10,542 --> 00:01:14,511
Karger's contraction algorithm is, it
showed that random sampling can be

20
00:01:14,511 --> 00:01:19,406
extremely effective for fundamental graph
problems. >>So here's how it works. We're

21
00:01:19,406 --> 00:01:24,315
just gonna have one main loop. Each
iteration of this while-Loop is going to

22
00:01:24,315 --> 00:01:27,689
decrease the number of vertices in the
graph by 1, and we're gonna terminate

23
00:01:27,689 --> 00:01:31,677
when we get down to just two vertices
remaining. Now, in a given iteration,

24
00:01:31,677 --> 00:01:35,987
here's the random sampling: amongst all of
the edges that remain in the graph to this

25
00:01:35,987 --> 00:01:40,266
point, we're going to choose one of those
edges uniformly at random. Each edge is

26
00:01:40,266 --> 00:01:45,743
equally likely. Once you've chosen an
edge, that's when we do the contraction.

27
00:01:45,743 --> 00:01:50,582
So we take the two endpoints of the edge,
call them the vertex u and the vertex v,

28
00:01:50,582 --> 00:01:55,540
and we fuse them into a single vertex that
represents both of them. This may become

29
00:01:55,540 --> 00:02:00,080
more clear when I go through a couple
examples on the next couple of slides.

30
00:02:00,080 --> 00:02:04,130
This merging may create parallel edges,
even if you didn't have them before.

31
00:02:04,130 --> 00:02:06,994
That's okay. We're gonna leave the
parallel edges. And it may create a

32
00:02:06,994 --> 00:02:11,446
self-loop edge pointer that both of the endpoints
is the same. And self-loops are

33
00:02:11,446 --> 00:02:15,842
stupid, so we're just gonna delete as they
arise. Each generation decreases the

34
00:02:15,842 --> 00:02:20,024
number of vertices that remain. We start
with N vertices. We end up with 2. So

35
00:02:20,024 --> 00:02:24,344
after N-2 generations, that's when
we stop and at that point we return the

36
00:02:24,344 --> 00:02:29,927
cuts represented by those two final
vertices. You might well be wondering what

37
00:02:29,927 --> 00:02:34,034
I mean by the cut represented by the final
two vertices. But I think that will become

38
00:02:34,034 --> 00:02:38,746
clear in the examples, which I'll proceed
to now. >>So suppose the input graph

39
00:02:38,746 --> 00:02:45,530
is the following four node, four edge
graph. There's a square plus one diagonal.

40
00:02:45,530 --> 00:02:49,783
So, how would the contraction algorithm
work on this graph? Well, of course, it's

41
00:02:49,783 --> 00:02:52,670
a randomized algorithm so it could work in
different ways. And so, we're gonna look

42
00:02:52,670 --> 00:02:55,971
at two different trajectories. In the
first iteration each of these five edges

43
00:02:55,971 --> 00:02:59,057
is equally likely. Each is chosen for
contraction with twenty percent

44
00:02:59,057 --> 00:03:03,658
probability. For concreteness, let's say
that the algorithm happens to choose this

45
00:03:03,658 --> 00:03:09,721
edge to contract, to fuse the two
endpoints. After the fusion these two

46
00:03:09,721 --> 00:03:13,892
vertices on the left have become one,
whereas the two vertices on the right are

47
00:03:13,892 --> 00:03:19,145
still hanging around like they always
were. So, the edge between the two

48
00:03:19,145 --> 00:03:23,882
original vertices is unchanged. The
contracted edge between the two vertices on the left

49
00:03:23,882 --> 00:03:30,350
has gotten sucked up, so that's gone. And
so what remains are these two edges here.

50
00:03:30,350 --> 00:03:36,328
The edge on top, and the diagonal. And
those are now parallel edges, between the

51
00:03:36,328 --> 00:03:40,752
fused node and the upper right node. And
then I also shouldn't forget the bottom

52
00:03:40,752 --> 00:03:49,258
edge, which is edge from the lower right
node to the super node. So that's what we

53
00:03:49,258 --> 00:03:53,303
mean by taking a pair of the vertices and
contracting them. The edge that was

54
00:03:53,303 --> 00:03:56,840
previously connected with them vanishes,
and then all the other edges just get

55
00:03:56,840 --> 00:04:01,428
pulled into the fusion. >>So that's the
first iteration of Karger's algorithm of

56
00:04:01,428 --> 00:04:05,626
one possible execution. So now we proceed
to the second iteration of the contraction

57
00:04:05,626 --> 00:04:08,983
algorithm, and the same thing happens all
over again. We pick an edge, uniformly at

58
00:04:08,983 --> 00:04:12,204
random. Now there's only four edges that
remain, each of which is equally likely to

59
00:04:12,204 --> 00:04:16,971
be chosen, so the 25% probability.
For concreteness, let's say that in the

60
00:04:16,971 --> 00:04:21,520
second iteration, we wind up choosing one
of the two parallel edges, say this one

61
00:04:21,520 --> 00:04:25,712
here. So what happens? Well, now, instead
of three vertices, we go down to 2. We

62
00:04:25,712 --> 00:04:31,128
have the original bottom right vertex that
hasn't participated in any contractions at

63
00:04:31,128 --> 00:04:35,651
all, so that's as it was. And then we have
the second vertex, which actually

64
00:04:35,651 --> 00:04:40,940
represents diffusion of all of the other
three vertices. So two of them were fused,

65
00:04:40,940 --> 00:04:44,115
the leftmost vertices were fused in
iteration 1. And now the upper right

66
00:04:44,115 --> 00:04:48,514
vertex got fused into with them to create
this super node representing three

67
00:04:48,514 --> 00:04:52,936
original vertices. So, what happens to the
four edges? Well, the contracted one

68
00:04:52,936 --> 00:04:55,770
disappears. That just gets sucked into the
super node, and we never see it again.

69
00:04:55,770 --> 00:05:00,002
Again, and then the other three go, and
where there's, go where they're supposed

70
00:05:00,002 --> 00:05:05,374
to go. So there's the edge that used to be
the right most edge. That has no hash

71
00:05:05,374 --> 00:05:09,668
mark. There's the edge with two hash
marks. That goes between the, the same two

72
00:05:09,668 --> 00:05:13,047
nodes that it did before. Just the super
node is now an even bigger node

73
00:05:13,047 --> 00:05:16,848
representing three nodes. And then the
edge which was parallel to the one that we

74
00:05:16,848 --> 00:05:21,574
contracted, the other one with a hash mark
becomes a self-loop. And remember what

75
00:05:21,574 --> 00:05:25,646
the, what the algorithm does is, whenever
self loops like this appear, they get

76
00:05:25,646 --> 00:05:30,103
deleted automatically. And now that we've
done our N-2 iterations, we're

77
00:05:30,103 --> 00:05:33,336
down to just two nodes. We return the
corresponding cut. By corresponding cut,

78
00:05:33,336 --> 00:05:38,633
what I mean is, one group of the cut is
the vertices that got fused into each

79
00:05:38,633 --> 00:05:43,116
other, and wound up corresponding to the
super node. In this case, everything but

80
00:05:43,116 --> 00:05:47,654
the bottom right node, And then the other
group is the original nodes corresponding

81
00:05:47,654 --> 00:05:51,321
to the other super node of the contracted
graphs, which, in this case, in just the

82
00:05:51,321 --> 00:05:57,710
bottom right node by itself. So this Set A
is going to be these three nodes here,

83
00:05:57,710 --> 00:06:01,762
which all got fused into each other,
contracted into each other. And B is going

84
00:06:01,762 --> 00:06:06,467
to be this node over here which never
participated in any contractions at all.

85
00:06:06,467 --> 00:06:12,594
And what's cool is, you'll notice, this
does, in fact, define a min cut. There are

86
00:06:12,594 --> 00:06:18,517
two edges crossing this cut. This one, the
rightmost one and the bottommost one. And

87
00:06:18,517 --> 00:06:22,748
I'll leave it for you to check that there
is no cut in this graph with fewer than

88
00:06:22,748 --> 00:06:29,925
two crossing edges, so this is in fact a
min cut. >>Of course, this is a randomized

89
00:06:29,925 --> 00:06:33,178
algorithm, and randomized algorithms can
behave differently on different

90
00:06:33,178 --> 00:06:36,833
executions. So let's look at a second
possible execution of the contraction

91
00:06:36,833 --> 00:06:41,917
algorithm on this exact same input. Let's
even suppose the first iteration goes

92
00:06:41,917 --> 00:06:46,705
about in exactly the same way. So, in
particular, this leftmost edge is gonna

93
00:06:46,705 --> 00:06:50,084
get chosen in the first iteration. Then
instead of choosing one of the two

94
00:06:50,084 --> 00:06:55,068
parallel edges, which suppose that we
choose the rightmost edge to contract in

95
00:06:55,068 --> 00:06:59,194
the second iteration. Totally possible, 25%
chance that it's gonna happen. Now

96
00:06:59,194 --> 00:07:03,697
what happens after the contraction? Well,
again, we're gonna be left with two nodes,

97
00:07:03,697 --> 00:07:08,135
no surprise there. The contracted node
gets sucked into oblivion and vanishes.

98
00:07:08,135 --> 00:07:13,584
But the other three edges, the ones with
the hash marks, all stick around, and

99
00:07:13,584 --> 00:07:18,487
become parallel edges between these two
final nodes. This, again, corresponds to a

100
00:07:18,487 --> 00:07:27,852
cut (A, B), where A is the left two
vertices, and B is the right two vertices.

101
00:07:27,852 --> 00:07:34,266
Now, this cut you'll notice has three
crossing edges, and we've already seen that

102
00:07:34,266 --> 00:07:40,325
there is a cut with two crossing edges.
Therefore, this is <i>not</i> a min cut. >>So what

103
00:07:40,325 --> 00:07:44,503
have we learned? We've learned that,
the contractual algorithm sometimes

104
00:07:44,503 --> 00:07:49,127
identifies the min cut, and sometimes it
does not. It depends on the random choices

105
00:07:49,127 --> 00:07:53,529
that it makes. It depends on which edges
it chooses to randomly contract. So the

106
00:07:53,529 --> 00:07:57,930
obvious question is, you know, is this a
useful algorithm. So in particular, what

107
00:07:57,930 --> 00:08:02,559
is the probability that it gets the right
answer? We know it's bigger than 0, and

108
00:08:02,559 --> 00:08:07,913
we know it's less than 1. Is it close to
1, or is it close to 0? So we find

109
00:08:07,913 --> 00:08:11,454
ourselves in a familiar position. We have
what seems like a quite sweet

110
00:08:11,454 --> 00:08:15,092
algorithm, this random contraction
algorithm. And we don't really know if

111
00:08:15,092 --> 00:08:18,458
it's good or not. We don't really know how
often it works, and we're going to need to

112
00:08:18,458 --> 00:08:21,190
do a little bit of math to answer that
question. So in particular, we'll need

113
00:08:21,190 --> 00:08:25,634
some conditional probability. So for those
of you, who need a refresher, go to your

114
00:08:25,634 --> 00:08:29,239
favorite source, or you can watch the
Probability Review Part II, to get a

115
00:08:29,239 --> 00:08:33,353
refresher on conditional probability and
independence. Once you have that in your

116
00:08:33,353 --> 00:08:37,900
mathematical toolbox, we'll be able to
totally nail this question. Get a very

117
00:08:37,900 --> 00:08:42,038
precise answer to exactly how frequently
the contraction algorithm successfully

118
00:08:42,038 --> 00:08:44,120
computes the minimum cut.