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.