In this sequence of videos we're going to discuss an important, if somewhat poorly understood, approach to tackling NP complete problems namely local search. Before I discuss the general principals of local search algorithms, I want to begin with a concrete example that's going to be to the maximum cut problem. Some of you might remember that we studied the minimum cut problem in part one of the course, in particular, Carver's randomized contraction algorithm. That problem was defined as seeking out the cut of the graph that minimizes the number of crossing edges. The maximum cut problem, naturally enough, we want the cut that maximizes the number of crossing edges. More precisely, we're given, as input, an undirected graph g. And the responsibility of the algorithm is to output a cut that is a partition of the vertices into two non-empty sets, A and B, that maximizes the number of edges that have exactly one endpoint in each of the two groups of the partition. In the quiz on the next slide I'll give you an example to make sure that this definition makes sense. Before that just a couple of quick comments. So first, sadly, unlike the minimum cut problem which we saw in part one is computationally tractable, the maximum cut problem, in general, is computationally intractable, it's NP-complete. More precisely, the decision version of the question where you're given a graph you want to know whether or not there exists a cut that cuts at least a certain number of edges, that's an NP-complete problem. There's no polynomial time algorithm for it unless P equals NP. Like most NP-complete problems, there are some computational tractable special cases. For example the case of bipartite graphs. One definition of a bipartite graph is a graph in which there exists a cut, so that every single edge is crossing it. And then obviously, that would be the maximum cut of the graph. A slick way to solve this problem in linear time is to use breadth-first search. You just root the breadth-first search at a arbitrary vertex of the graph. You draw for your breadth-first search tree. You put the even layers as one of your groups A. You take the odd layers and make it the other group B. This will have no crossing edges, if and only if, the graph is bipartite. To make sure the definition of the maximum cut problem makes sense, what is the maximum cut in the following six-vertex graph? So the correct answer is c, 8. That's because the graph is bipartite. Only 8 edges and there is indeed a cut in which every single one of those edges crosses it. Specifically, take one group to the vertices w, n, x, and take the group B to be the vertices u, v, y and z. There are no edges internal to A, there are no edges internal to B. Every edge has one endpoint in each. So while the max cut problem is computationally tractable in bipartite graphs like this one using breadth-first search, it's NP-complete in general. More over, breath-first search turns out to be not a very good heuristic for approximating the maximum cut problem in general graphs. We're going to have to turn to other techniques. There's a number of interesting heuristics for the maximum cut problem. But I want to use the problem here to showcase the technique of local search. Local search is a general heuristic design paradigm. But I don't want to describe it in general until the following video, after we've gone through this concrete example. But at a higher level, you should think of it that we're always maintaining a candidate cut. And we just want to iteratively make it better and better via small, that is local, modifications. To succinctly state the algorithm I'm going to need a little bit of notation. So imagine that we have some undirected graph and we're trying to approximate the maximum cut. And suppose we have some current candidate cut A,B. Some of the vertices are in A the rest are in B. Now focus on some arbitrary vertex v, v can be an A or B I don't care. There is some incident edges to this vertex v, in the graph on the right, I've shown you a vertex v, it has degree five, five incident edges. Now, some of these edges are crossing the cut, some of the edges are not. So I'm going to use the notation c sub v (A, B) to denote the number of v's incident edges that are crossing the cut. And d sub v (A, B) to denote the edges, the number of edges which are not crossing the cut. So in the picture that I've drawn, c sub v would be equal to two, d sub v would be equal to three. Here then is the local search algorithm for maximum cut. In step one, we just begin with an arbitrary cut of the graph, so we just somehow, I don't care how, put some of the vertices in A, some of the vertices in B. Now, we just iteratively try to make the cut that we're working with better until we don't see any easy way to improve it further. So what's a principled way to take a given cut and make it better? Well, let's just focus on very simple modifications. Let's suppose the only thing we're allowed to do is take a vertex from one of the two groups say, from group A, and move it to group b. For example, in the green network I've showed you on the right-hand part of this slide, if we envision taking the vertex v and moving it from A to B, we get a superior cut. Why is that true? Well here are the two ramifications of moving v from A to B. So, first of all, the two edges incident to v that used to be crossing the cut, they no longer cross the cut. When we put v over on the right hand side the two edges who's other end points are in B those edges get sucked in internally to B. They are no longer crossing the cut. On the other hand, the good news is, is that the three edges incident to v with the other endpoint in A they used to be internal to the group A, but when we bring v over to the right hand side to the group B, now those three edges cross the cut. So we lost two edges from the cut but we gained three so that's a net improvement of one more edge crossing the cut. In general this argument shows that for any vertex so that the number of edges incident to it that are not crossing the cut, if that's bigger than the number which are crossing the cut incident to it, Then switching sides with that vertex will improve the cut. And the improvement is exactly the difference between the two quantities d sub v and c sub v. If we find ourself with a cut such that there's no vertex switch that improves the cut, that is if d sub v and (A, B) is at most c sub v of (A, B) for every single vertex v. Then we stop and we just return to the cut that we ended up with. We typically evaluate algorithms along two axes. First of all, how good is their solution? So, for example, is the algorithm always correct, or at least approximately correct? And secondly, what resources does it require? So, for example, is the running time reasonable? Now to be honest local search algorithms often perform poorly at least in the worst case along both of these criteria. This local search algorithm for the maximum cut problem is interesting in that we can say non-trivial positive things both about the solution quality and about its running time. The running time bound follows easily from an observation that we made earlier. Namely that every time we do an iteration of the while loop, every time we switch a vertex from one side to the other, the number of crossing edges goes up necessarily by at least one. So I'm going to assume that the graph is simple, that there's no parallel edges. In which case, there's at most n choose 2 edges in the graph, that means that this while loop can only execute in total an n choose 2 or quadratic number of times. It's easy to implement each iteration of the while loop quickly, so that means this overall algorithm will terminate in polynomial time. Now this local search algorithm does not solve the maximum cut problem optimally. It does not guarantee to return the maximum cut. Indeed, that would be way to much to hope for now that we know that it runs in polnomial time. Remember the maximum cut problem is NP-complete. However, interestingly, this is a heuristic with a good worse case performance guarantee. Precisely the outcome of this local search algorithm is guaranteed to be a cut in which the number of crossing edges is at least half, at least 50% of the maximum possible. In fact, something stronger is true. It's even guaranteed to be at least 50% of all of the edges of the graph. Which of course is an upper bound on the maximum number of edges crossing some cut.
