0:04

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.

0:23

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.

0:42

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.

1:00

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.

1:50

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.

2:38

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.

2:55

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.

3:22

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.

3:42

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.

4:33

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.

4:54

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.

6:19

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.

6:35

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.

7:40

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.