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 principles 
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, 
Carter'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 cuts that 
is a partition of the vertices into two 
nonempty 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, will 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 is no polynomial time algorithm for 
it unless p equals np. 
Like most NP-complete problems, there are 
some computationally 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 is 
linear, in linear time is to use 
breadth-first search. 
You just root the breadth-first search in 
an arbitrary vertex of the graph. 
You draw your breadth-first search tree. 
You put the even layers as one of your 
groups A, you take your 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. 
There's only eight edges and there is 
indeed a cut, in which every single one 
of those edges crosses it. 
Specifically, take one group to be the w 
and 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, well the max cut problem is 
computationally tractable in bipartite 
graphs like this one using firstbreadth- 
search. 
It's NP-complete in general, moreover, 
breadth-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 high level, you should think of 
it as 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's some incident edges to this 
vertex V. 
In the graph on the right, I've shown you 
a vertex V. 
It has degree 5, 5 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 Vs incident 
edges that are crossing the cut, and D 
sub V (A,B) to denote the edge, the 
number of edges that are not crossing the 
cut. 
So in the picture that I've drawn, C sub 
V would be equal to 2, 
D sub v would be equal to 3. 
Here then, is the local search algorithm, 
for maximum cut. 
In step 1, we just begin with an 
arbitrary cut of the graph. 
So we just, somehow, I don't care how, 
but some of the vertices of 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, lets 
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 
shown 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 whose other endpoints 
are in B, those edges get sucked in, 
internal 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 of 
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 
that 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 ourselves with a cut, such 
that theres no vertex switch that 
improves the cut, that is D sub V of AB 
is at most C sub V of AB 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 axis. 
So 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? 
And 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 nontrivial 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 a 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 two 
edges in the graph. 
That means that this while loop can only 
execute in total, an N choose two or 
quadratic number of times. 
It's easier 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 is not guaranteed to return the 
maximum cut. 
Indeed, that will be way too much to hope 
for now that we know that it runs in 
polynomial time. 
Remember, the maximum cut problem is 
NP-complete. 
However, interestingly, this is a 
heuristic with a good worst case 
performance guarantee. 
Precisely the outcome of this logo search 
algorithm is guaranteed, guaranteed to be 
a cut in which the number of crossing 
edges is a 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.