0:00
We now come to a more interesting reduction that connects Boolean logic
to graphs.
Namely we are going to reduce this 3-SAT [INAUDIBLE] problem,
there is an independent set problem.
Recall that in the 3-SAT problem,
our input is a formula in 3-CNF, that is a collection of clauses.
Each clause is a disjunction of at most three literals.
And our goal is to check whether it is possible to assign Boolean values
to all the variables of the formula F, so that to satisfy all the given clauses.
0:40
Since we need to reduce this to the independent set problem our goal
is to polynomial logarithm that takes the formula F in 3-CNF.
And outputs a graph G and an integer b such that
the input formula F is satisfiable, if and only if,
there is an independent set of size at least b in the graph G.
1:25
The given example, consider the following formula.
It is satisfied by an assignment which assigns the value true as value 1 to
all the variables.
Indeed, in the first clause we have just all
the literals in the first clause are satisfied.
In the second clause, the first literal is satisfied by this truth assignment.
And in the last clause,
the first literal is also satisfied by this truth assignment.
1:54
Then with another assignment that satisfies the same formula,
namely if I assign the value 1 to x and the value 0 to y and z.
We satisfy the first literal in the first clause,
we satisfy both literals in the second clause, and
we satisfy the last literal in the last clause.
This point of view gives us an alternative definition of the satisfiability problem.
Namely to satisfy a given CNF formula, we need to select from each clause
of a given formula one literal, such as the resulting said of selected.
Literals is consistent, meaning that it doesn't contain a literal L,
together with its negation.
Let me illustrate this on a toy example, as usual.
Assume that we have a formula consistent of three clauses over variables x,
y, and z.
Well by consistent set of literals in this case, we mean for example x, x and not z.
2:59
So this is one, so from first clause we select the literal x, from the second one
we also select the literal x, and from the third clause we select the literal not z.
Note that for these consistent set of literals,
we can find the corresponding satisfying assignment.
Namely, we assign value 1 to x, and the value 0 to z.
Namely, we satisfy all the literal in this set.
So for this we assign the value 1 to x and value 0 to z.
It is easy to see that this is indeed a satisfying assignment.
So in the first clause x is satisfied on the second clause,
x is satisfied on the last clause not z inside this fight.
It was the value of y doesn't actually matter in this case.
We can get a the full consistent set of literal just by selecting x and
from the first clause x from the second clause, and y from the third clause.
4:04
And as a possibility is to select x from the first one,
not y from the second one and not z from the third one.
This will give us the following constant set of literals.
Once again, we want this set of literals to be consistent so
that we are able to assign a specific value for reach literal.
So for this, to explain this better
let's consider some inconsistent sets of literals.
Assume that from the first clause we select not y,
from the second clause we select the negation of y from the second,
from the third clause we select not z.
So this gives us the following set of literals,
which is inconsistent because It contains was y and a negation of y.
In this case, we can not assign
the value to y to satisfy all the laterals in this clause.
Namely if we assigns a value 0 to y, then we falsify this literal y.
If we assign the value 1 to y, we falsify this literal in this clause.
And this is exactly the reason why we would like our set of selected literals
to be consistent.
This alternative statement of the satisfiability problem is the main idea,
is the main ingredient of our reduction from 3-SAT to
the independent set problem problem.
We illustrate the reduction first on a toy example as usual.
Given a formula in this case with five clauses,
so with three variables, x y and z.
The first step is to introduce for each clause two or
three new vertices labeled with the literals of this clause.
In this case, it gives us the following picture.
So x, y and z here correspond to this clause.
5:58
X and not y here respond to this clause the last
three vertices to respond to this clause and so on.
The next thing to do is to join all the vertices,
all the pairs of vertices inside each block.
So for those three clauses, we have two triangles and
for those two clauses, we have just three edges.
6:25
Once again, each three clause corresponds to a triangle,
each two clause, that is clause of length two corresponds to a single edge.
So all these edges actually, what am I going to do,
is to find a large independent set in this graph.
And all the newly added edges force us to
select into our independent set at most one vertex from each block.
For example we cannot select two vertices from this block you aren't
doing independent set because any two of them are joined by an edge.
The same is for this block, for example.
We can only select just one vertex from this block into an independent set,
because they are connected by en edge.
7:14
So selecting a vertex from each of these blocks into an independent set,
corresponds to selecting a literal from the corresponding clause,
that is going to be satisfied in this clause.
We call that in each clause we need to select a literal which is going to satisfy
this clause.
So we mimic this by selecting the corresponding vertex from a block.
However, recall that we need to select a consistent set of literals.
That is we do not want to select for example,
was x from some clause and not x from some other clause.
To force our set of selected vertices to
be labeled with consistent set of literals,
we just add all possible edges between all pairs of complementary literals.
Namely, whenever we have a vertex labeled with x like this one, and
not x kike this one, we join them by an edge.
So we have x here, we have not x here, we join them by an edge.
Another pair of vertices x here and not x here.
We also join them by an edge, then there is another vertex labeled by x,
we'll also join them by an edge, x and not x and z this not x.
And we do this for all of the pairs of complementary literals.
Now, the claim is that this graph contains an independent set of sides.
Exactly 5 or at least 5 if and only if the initial formula is satisfiable.
8:55
And it is already clear, so if the formula is satisfiable,
this means that for each clause we can select one literal
such that the resulting set of literals is consistent.
But this also means that from each of these five block, so
this is the first block, corresponding to the first block, this is the second,
this is the third one, this is the fourth one, this is the fifth one.
We can select exactly the same vertex that corresponds to the selected
literal in this formula.
So if the formula is satisfiable, then in each block we can select on vertex.
And we know that they are not going to be joined by edges,
because vertices from different blocks are only joined if they are complementary.
And we know that our set of literals does not contain complimentary literals.
So if the formula is satisfiable,
then this graph contains an independent set of size 5.
And vice versa uses graph contents an independent set of size 5 and
the formula is satisfied both.
Why is that?
Well just because any independent set of size 5
has exactly 1 various of nature of these blocks.
And we know that the labels of these vertices give us a set of
literals which is consistent, which doesn't contain
a literal together with it's complementary literal.
So it gives us a set of literals such that it
intersects every clause of our initial formula.
Which means that if the response,
they are satisfying the assignment of the initial formula.
To summarize, let's state this reduction formally.
The reduction works as follows, given formula F in 3-CNF, that is
a collection of clauses, each of length at most three, what is the following?
We scan the set of the clauses from left to right and
for each clause, we introduce three or two,
or just one dependent on the number of literals in this clause.
Three or two, or one vertices, and we'll label them with
literals of this clause and we join every two of them by an edge.
So we are now constructing a graph G, and
this forces every independent set in this graph to contain
at most one vertex from each block to responding to a single clause.
11:31
Then we also need to force each independent set to be labeled with
a set of literals which is consist.
For this we do the following, we join every pair of vertices
in our graph which are labeled with complementary literals.
That is if I got axis labeled with a literal L, we add new addresses
that connect it to all vertices, which are labeled with a negation of L.
Then what we've just proved on it, our example is the following.
The resulting graph G contains an independent set of size B,
where B is the number of clauses of the initial formula
even though with the initial formula is satisfiable.
12:22
It remains to note that the running time of
the resulting transformation is polynomial.
Why is that?
Well just because to construct this graph we first just
scan the formula which takes linear time on the size of the formula.
It is just big O of the number of clauses,
to make it more formal let's denote by m the number of clauses and
in our formula then this step takes time O(m).
We just count the list of clauses and during this scan we introduce 3m vertices.
And then we need to check every pair of these vertices and to join them by
intersect if they're labeled by a complimentary pair of literals.
So the second step clearly takes time at most m squared.
In any case, this is polynomial so the wall transformation takes polynomial time.
Formally, we need also to describe an algorithm that transforms
any solution to the maximum independent set problem for
the resulting graph back to a solution to the three satisfiability problem.
And we also need to ensure that if there is no solution for
the resulting instance of the maximum independent set problems,
then there is no solution for the initial problem.
But this is not difficult, and we did this already.
Namely, if there is a solution for the resulting
instance of the maximum independent set problem and there is a maximum,
there is an independent set of size equal to the number of clauses.
That means that from each block we can select a vertex,
such that all the labels of these vertices is consistent.
If the consistent set of literals, but this also means that this gives
the satisfying assignment of the initial formula.
14:21
If on the other hand, there is no solution for the resulting instance of
the independent set problem, then we know that the initial formula is unsatisfiable.
Indeed if it were satisfiable, if there were a satisfying assignment for
the initial formula, then this would give us an independent
set in the graph of size equal to the number of clauses.
Which would contradict to the fact that there is
no such independent set in the resulting graph.
Alexander S. KulikovVisiting Professor
Michael LevinLecturer
Daniel M KaneAssistant Professor
Neil RhodesAdjunct Faculty
