
Title:
0909 Using Clique To Set Variables

Description:

There's 2 cases here; so let's say the graph does have a clique the size of m,

then what will happen is the following.

So it contains exactly 1 vertex

that corresponds to a variable in that clause,

and what we also know is

because we constructed the graph this way,

that we can not have 2 vertices connected here in this graph

where there's a conflict, so what we can not have in this graph, for example

is 1 vertex that represent not x2

and another vertex that represents x2,

because we avoided this in the construction

but this directly shows us how we can

satisfy this Boolean formula here,

so if we have a not x2 here, we just set it to 0

so we could just set this one to false,

so that not x2 becomes true,

then this clause here is satisfied

and also this one over here would be satisfied.

And x1that's a separate variable,

so we can set it as we want,

and we could set this one to false.

So we have x2

and we can set that to false so not x2 becomes true.

So that becomes true,

that one becomes true,

that one here is false.

Over here, we have not x2 as well,

so there's no conflict here.

x1we haven't yet talked about x1,

but can just do the same thing; we can set x1 to false,

so the whole thing not x1 becomes true.

We have set it to false,

and we haven't even looked at x3,

but all of the clauses are already satisfied,

and that's actually the cool thing to notice here.

x3 is also not contained in the clique,

so the vertices in the clique tell you

how to set the variables

so that the Boolean formula can be satisfied.

So what if this graph here does not have a clique of size m?

Well in this case, it means that

we have 1 clause group

which is not contained in the clique

and if we have 1 clause group that is not contained in the clique,

this means that there's no vertex

in the clause group

that has connections to all of the other vertices in the smaller clique

that we're looking for,

and that means, due to the way we constructed the graph,

that every vertex

has a conflict with

another vertex in the clique

so if there's no large clique,

this means that every assignment

of true and false of the variables will lead to a conflict

such that at least 1 of the clauses

can not be satisfied.

So then the Boolean formula does not have a satisfying assignment.

So now that we have this reduction,

we know that clique is

NP complete,

which of course makes Bob a little unhappy.

So now what about vertex independent set?

Are those problems NP complete

or are we not sure yet?