1 00:00:00,012 --> 00:00:04,851 In this sequence of videos, we're going to discuss an important if somewhat 2 00:00:04,851 --> 00:00:10,183 poorly understood approach to tackling NP-complete problems, namely local 3 00:00:10,183 --> 00:00:13,417 search. Before I discuss the general principles 4 00:00:13,417 --> 00:00:18,355 of local search algorithms, I want to begin with a concrete example that's 5 00:00:18,355 --> 00:00:22,592 going to be to the maximum cut problem. Some of you might remember that we 6 00:00:22,592 --> 00:00:26,507 studied the minimum cut problem in part one of the course, in particular, 7 00:00:26,507 --> 00:00:28,972 Carter's randomized contraction algorithm. 8 00:00:28,972 --> 00:00:33,247 That problem was defined as seeking out the cut of the graph that minimizes the 9 00:00:33,247 --> 00:00:36,557 number of crossing edges. The maximum cut problem, naturally 10 00:00:36,557 --> 00:00:40,452 enough, we want the cut that maximizes the number of crossing edges. 11 00:00:40,452 --> 00:00:45,612 More precisely, we're given as input an undirected graph g and the responsibility 12 00:00:45,612 --> 00:00:50,439 of the algorithm is to output a cuts that is a partition of the vertices into two 13 00:00:50,439 --> 00:00:55,191 nonempty sets, A and B, that maximizes the number of edges that have exactly one 14 00:00:55,191 --> 00:00:58,452 endpoint in each of the two groups of the partition. 15 00:00:58,452 --> 00:01:02,293 In the quiz on the next slide, will give you an example to make sure that this 16 00:01:02,293 --> 00:01:05,393 definition makes sense. Before that, just a couple of quick 17 00:01:05,393 --> 00:01:07,970 comments. So first, sadly, unlike the minimum cut 18 00:01:07,970 --> 00:01:11,742 problem, which we saw in part one, is computationally tractable, the maximum 19 00:01:11,742 --> 00:01:15,570 cut problem in general is computationally intractable, it's NP-complete. 20 00:01:15,570 --> 00:01:19,591 More precisely, the decision version of the question where you're given a graph, 21 00:01:19,591 --> 00:01:23,625 you want to know whether or not there exists a cut that cuts at least a certain 22 00:01:23,625 --> 00:01:26,034 number of edges, that's an NP-complete problem. 23 00:01:26,034 --> 00:01:29,507 There is no polynomial time algorithm for it unless p equals np. 24 00:01:29,507 --> 00:01:34,657 Like most NP-complete problems, there are some computationally tractable special 25 00:01:34,657 --> 00:01:37,777 cases. For example the case of bipartite graphs. 26 00:01:37,777 --> 00:01:42,822 One definition of a bipartite graph is a graph in which there exists a cut so that 27 00:01:42,822 --> 00:01:47,232 every single edge is crossing it, and then obviously, that would be the 28 00:01:47,232 --> 00:01:51,018 maximum cut of the graph. A slick way to solve this problem is 29 00:01:51,018 --> 00:01:53,915 linear, in linear time is to use breadth-first search. 30 00:01:53,915 --> 00:01:57,856 You just root the breadth-first search in an arbitrary vertex of the graph. 31 00:01:57,856 --> 00:02:01,961 You draw your breadth-first search tree. You put the even layers as one of your 32 00:02:01,961 --> 00:02:05,407 groups A, you take your odd layers and make it the other group, B. 33 00:02:05,407 --> 00:02:10,821 This will have no crossing edges if and only if the graph is bipartite. 34 00:02:10,821 --> 00:02:17,024 To make sure the definition of the maximum cut problem makes sense, what is 35 00:02:17,024 --> 00:02:23,503 the maximum cut in the following six vertex graph? So the correct answer is C, 36 00:02:23,503 --> 00:02:27,486 8, that's because the graph is bipartite. 37 00:02:27,486 --> 00:02:34,219 There's only eight edges and there is indeed a cut, in which every single one 38 00:02:34,219 --> 00:02:41,158 of those edges crosses it. Specifically, take one group to be the w 39 00:02:41,158 --> 00:02:44,176 and x, and take the group B to be the vertices 40 00:02:44,176 --> 00:02:47,499 u, v, y, and z. There are no edges internal to A, there 41 00:02:47,499 --> 00:02:51,349 are no edges internal to B, every edge has one endpoint in each. 42 00:02:51,349 --> 00:02:55,789 So, well the max cut problem is computationally tractable in bipartite 43 00:02:55,789 --> 00:02:58,843 graphs like this one using firstbreadth- search. 44 00:02:58,843 --> 00:03:03,634 It's NP-complete in general, moreover, breadth-first search turns out to be not 45 00:03:03,634 --> 00:03:08,482 a very good heuristic for approximating the maximum cut problem in general 46 00:03:08,482 --> 00:03:11,952 graphs. We're going to have to turn to other techniques. 47 00:03:11,952 --> 00:03:16,583 There's a number of interesting heuristics for the maximum cut problem, 48 00:03:16,583 --> 00:03:21,622 but I want to use the problem here to showcase the technique of local search. 49 00:03:21,622 --> 00:03:24,502 Local search is a general heuristic design paradigm, 50 00:03:24,502 --> 00:03:28,535 but I don't want to describe it in general until the following video, after 51 00:03:28,535 --> 00:03:33,056 we've gone through this concrete example. But, at a high level, you should think of 52 00:03:33,056 --> 00:03:36,567 it as we're always maintaining a candidate cut and we just want to 53 00:03:36,567 --> 00:03:41,572 iteratively make it better and better via small, that is local, modifications. 54 00:03:41,572 --> 00:03:45,475 To succinctly state the algorithm, I'm going to need a little bit of notation. 55 00:03:45,475 --> 00:03:49,714 So, imagine that we have some undirected graph and we're trying to approximate the 56 00:03:49,714 --> 00:03:53,642 maximum cut, and suppose we have some current candidate cut A,B, some of the 57 00:03:53,642 --> 00:03:58,175 vertices are in A, the rest are in B. Now, focus on some arbitrary vertex V. 58 00:03:58,175 --> 00:04:02,567 V can be an A or B, I don't care. There's some incident edges to this 59 00:04:02,567 --> 00:04:05,885 vertex V. In the graph on the right, I've shown you 60 00:04:05,885 --> 00:04:08,911 a vertex V. It has degree 5, 5 incident edges. 61 00:04:08,911 --> 00:04:13,492 Now, some of these edges are crossing the cut, some of the edges are not. 62 00:04:13,492 --> 00:04:18,496 So I'm going to use the notation C sub V (A,B) to denote the number of Vs incident 63 00:04:18,496 --> 00:04:23,017 edges that are crossing the cut, and D sub V (A,B) to denote the edge, the 64 00:04:23,017 --> 00:04:25,889 number of edges that are not crossing the cut. 65 00:04:25,889 --> 00:04:29,589 So in the picture that I've drawn, C sub V would be equal to 2, 66 00:04:30,660 --> 00:04:34,783 D sub v would be equal to 3. Here then, is the local search algorithm, 67 00:04:34,783 --> 00:04:37,604 for maximum cut. In step 1, we just begin with an 68 00:04:37,604 --> 00:04:41,574 arbitrary cut of the graph. So we just, somehow, I don't care how, 69 00:04:41,574 --> 00:04:44,829 but some of the vertices of A, some of the vertices in B. 70 00:04:44,829 --> 00:04:49,517 Now, we just iteratively try to make the cut that we're working with better, until 71 00:04:49,517 --> 00:04:52,531 we don't see any easy way to improve it further. 72 00:04:52,531 --> 00:04:57,164 So, what's a principled way to take a given cut and make it better? Well, lets 73 00:04:57,164 --> 00:05:01,647 just focus on very simple modifications. Let's suppose the only thing we're 74 00:05:01,647 --> 00:05:06,132 allowed to do is take a vertex from one of the two groups, say from group A and 75 00:05:06,132 --> 00:05:09,584 move it to group B. For example, in the green network, I've 76 00:05:09,584 --> 00:05:14,299 shown you on the right-hand part of this slide, if we envision taking the vertex 77 00:05:14,299 --> 00:05:17,495 V, and moving it from A to B, we get a superior cut. 78 00:05:17,495 --> 00:05:22,248 Why is that true? Well, here are the two ramifications of moving V from A to B. 79 00:05:22,248 --> 00:05:27,001 So first of all, the two edges incident to V that used to be crossing the cut, 80 00:05:27,001 --> 00:05:31,033 they no longer cross the cut. When we put V over on the right-hand 81 00:05:31,033 --> 00:05:35,886 side, the two edges whose other endpoints are in B, those edges get sucked in, 82 00:05:35,886 --> 00:05:38,790 internal to B, they are no longer crossing the cut. 83 00:05:38,790 --> 00:05:43,010 On the other hand, the good news is, is that the three edges incident to V, with 84 00:05:43,010 --> 00:05:47,292 the other endpoint in A, they used to be internal to the group A, but when we 85 00:05:47,292 --> 00:05:51,400 bring V over to the right-hand side of the group B, now those three edges cross 86 00:05:51,400 --> 00:05:54,044 the cut. So we lost two edges from the cut, but we 87 00:05:54,044 --> 00:05:58,637 gained three, so that's a net improvement of one more edge crossing the cut. 88 00:05:58,637 --> 00:06:03,022 In general, this argument shows that for any vertex, so that the number of edges 89 00:06:03,022 --> 00:06:07,262 incident to it that are not crossing the cut, if that's bigger than the number 90 00:06:07,262 --> 00:06:11,597 that are crossing the cut incident to it, then switching sides with that vertex 91 00:06:11,597 --> 00:06:17,128 will improve the cut and the improvement is exactly the difference between the two 92 00:06:17,128 --> 00:06:21,682 quantities, D sub V and C sub V. If we find ourselves with a cut, such 93 00:06:21,682 --> 00:06:26,692 that theres no vertex switch that improves the cut, that is D sub V of AB 94 00:06:26,692 --> 00:06:30,834 is at most C sub V of AB for every single vertex V, 95 00:06:30,834 --> 00:06:34,223 then we stop, and we just return to the cut that we ended up with. 96 00:06:34,223 --> 00:06:36,703 We typically evaluate algorithms along two axis. 97 00:06:36,703 --> 00:06:39,030 So first of all, how good is their solution? 98 00:06:39,030 --> 00:06:42,971 So, for example, is the algorithm always correct or at least approximately 99 00:06:42,971 --> 00:06:47,183 correct? And secondly, what resources does it require? So, for example, is the 100 00:06:47,183 --> 00:06:50,642 running time reasonable? And to be honest, local search algorithms 101 00:06:50,642 --> 00:06:54,292 often perform poorly, at least in the worst case, along both of these criteria. 102 00:06:54,292 --> 00:06:57,692 This local search algorithm for the maximum cut problem is interesting in 103 00:06:57,692 --> 00:07:01,267 that we can say nontrivial positive things both about the solution quality 104 00:07:01,267 --> 00:07:04,317 and about its running time. The running time bound follows easily 105 00:07:04,317 --> 00:07:08,167 from an observation that we made earlier, namely that every time we do an iteration 106 00:07:08,167 --> 00:07:11,967 of the while loop, every time we switch a vertex from one side to the other, the 107 00:07:11,967 --> 00:07:15,684 number of crossing edges goes up, necessarily, by a at least one. 108 00:07:15,684 --> 00:07:19,854 So I'm going to assume that the graph is simple, that there's no parallel edges in 109 00:07:19,854 --> 00:07:22,847 which case there's at most N choose two edges in the graph. 110 00:07:22,847 --> 00:07:26,644 That means that this while loop can only execute in total, an N choose two or 111 00:07:26,644 --> 00:07:30,225 quadratic number of times. It's easier to implement each iteration 112 00:07:30,225 --> 00:07:34,693 of the while loop quickly, so that means this overall algorithm will terminate in 113 00:07:34,693 --> 00:07:38,902 polynomial time. Now, this local search algorithm does not 114 00:07:38,902 --> 00:07:43,788 solve the maximum cut problem optimally. It is not guaranteed to return the 115 00:07:43,788 --> 00:07:46,943 maximum cut. Indeed, that will be way too much to hope 116 00:07:46,943 --> 00:07:50,339 for now that we know that it runs in polynomial time. 117 00:07:50,339 --> 00:07:54,487 Remember, the maximum cut problem is NP-complete. 118 00:07:54,487 --> 00:07:58,912 However, interestingly, this is a heuristic with a good worst case 119 00:07:58,912 --> 00:08:03,362 performance guarantee. Precisely the outcome of this logo search 120 00:08:03,362 --> 00:08:08,662 algorithm is guaranteed, guaranteed to be a cut in which the number of crossing 121 00:08:08,662 --> 00:08:12,653 edges is a least half, at least 50% of the maximum possible. 122 00:08:12,653 --> 00:08:16,896 In fact, something stronger is true. It's even guaranteed to be at least 50% 123 00:08:16,896 --> 00:08:20,970 of all of the edges of the graph, which of course, is an upper bound on the 124 00:08:20,970 --> 00:08:22,803 maximum number of edges crossing some cut.