
Title:
1131 One Vertex In Solution

Description:

The correct answer here is, similar to vertex cover, those cases are actually the easy ones.

And I'll show you why.

Either v or u already has an assignment, and we can just consider 1 of those cases.

So let's say v already has an assignment, here is u, and there's 2 cases.

Either we said yes, v is in the independent set

or we say no, v is not in the independent set.

This case up here, that's very easy to see because if v is in the independent set

and there's an edge here between those vertices,

then you cannot be in the independent set.

So that one is very clear. What about the case down here?

That's a case that requires a little more thought.

By itself right now, it could either be that u is in the independent set or it's not.

And we don't know, so you might have been inclined to think

that we need to modify the search tree or initiate some other form of brute force search,

but actually, that's not necessary and I will show you why.

This vertex u here, there are 2 possibilities.

If u is not connected to any other vertices

so let's say all other vertices in the network are independent of u

then we can put u into the independent set without having to think

because we're looking for a maximum size independent set.

This is the only connection that u has to other vertices. Why not just take it?

It doesn't really cause any other conflicts.

Now, what if u is connected to other vertices?

Here there's 3 different possibilities.

The first possibility is that u has some neighboring vertex

so one that is connected by an edge

where we already have assigned it to be in the independent set.

And in that case we can immediately say no, you cannot be in the independent set.

We must assume that none of these vertices here is already in the independent set.

So now there is 2 different cases.

One is that 1 of these vertices here has not yet received an assignment.

And in that case we don't have to worry about modifying the search tree

because now we're looking at a case like this here again.

So we can use our standard search tree to search through assignments

for these 2 vertices here.

If every vertex here, on the other hand, already has an assignment,

then we just discussed, because we've just dealt with the other case,

that all of these assignments here must be a 0.

So all of these vertices hereand there can be more, of course

are not part of the independent set,

and that means that we can take u into the independent set again.

It might not have been obvious in terms of thinking it through what to do in this case,

but for an algorithm we can design it in a way

so that the algorithm always knows what it is to do.

First of all, it looks for edges where both vertices do not have an assignment.

And once it cannot find those edges anymore,

then it will know how to deal with the remaining vertices.

And this of course means that for independent set we can use a search tree that,

just like vertex cover, always finds an assignment for at least 2 vertices.

So its height, so to say, of the search tree is N/2.

The size of the layers multiplies by factor 3.

So the size of the overall tree is 3 to the power of N/2.

For independent set we have a search tree of size 1.733 to the power of N.

Just like vertex cover, the calculation here is the same.

And because independent set and clique are so similar,

we just have to transform the network to the inverse network,

as you remember, hopefully, from the first unit.

We also have a search tree of size 1.733 to the power of N for clique.

Just like Alice, no reason to be super happy,

but Bob and Carol can be a little happier now.

And of course we're going to go on investigating.