Theory of Computation
Lecture 30-31
Sarmad Abbasi
Virtual University
December 17, 2007
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 1/1
NP-completeness
In the last lecture we showed the following theorem.
Theorem
3SAT is NP-complete.
This is our second problem that we have shown to be NP-complete.
1 We now know that SAT is NP-complete.
2 We now know that 3SAT is NP-complete.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 2/1
NP-completeness
Note that 3SAT is a more restricted version of SAT. In 3SAT the formula
is in 3CNF. Which means that
1 The formula is given in conjunctive normal form.
2 Each clause has three literals.
So 3SAT is usually easier to work with than SAT.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 3/1
NP-completeness
Now, let us show that a problem from graph theory is NP-complete.
Note that so far we only know two problems that are NP-complete and
both are from propositional logic.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 4/1
NP-completeness
Now, let us show that a problem from graph theory is NP-complete.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 5/1
NP-completeness
Let us start by defining a problem that we will prove is NP-complete.
Let us first recall a definition from graph theory:
Definition
Let G = (V , E) be a graph. I ⊆ V is called an independent set if the
vertices in I have no edges between them. Thus for all x, y ∈ I where
x 6= y
{x, y } 6∈ E.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 6/1
NP-completeness
The figure shows a graph on 10 vertices. a, c, d, g is an independent
set.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 7/1
NP-completeness
The figure shows a graph on 12 vertices. b, c, f, j,k is an independent
set.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 8/1
Independent Sets
Let us define the following language:
IS = {hG, k ii : G has an independent set of size k }.
So computationally we have a problem in which we will be given:
1 A graph G.
2 and an integer k .
We have to find out if G has a independent set of size k .
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 9/1
Independent Sets
It is very easy to see that
IS ∈ NP.
We just have to give a verification algorithm. The details are your
homework.
Hint: It is easy to verify that a given set is an independent set in a
graph.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 10 / 1
Independent Sets
We want to show that IS is NP-complete. Now, all we have to do is to
show that
SAT ≤p IS.
Note that this is much easier than the proof of Cook-Levin theorem.
We only have to show that one problem is reducible to IS as opposed
to all the problems in NP. Let’s do that.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 11 / 1
Independent Sets
Theorem
SAT ≤p IS
Consequently IS is also NP-complete.
What do we want to do?
1 We will show that given a formula φ we can construct a graph Gφ
and an integer k such that
φ is satisfiable if and only if Gφ has an independent set of size k
As 3SAT is NP-complete we may assume that φ is in 3CNF.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 12 / 1
Independent Sets
Let us take the formula
(x1 ∨ x2 ∨ x3 ) ∧ (x1 ∨ x3 ∨ x5 ) ∧ (x3 ∨ x2 ∨ x5 )
and make the following graph.
1 For each clause place a cluster of vertices and connect them all to
eachother. Label each vertex with the literal in the clause.
2 Between clauses connect xi and xi .
Let us see how this graph is made.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 13 / 1
Independent Sets
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 14 / 1
Independent Sets
Suppose φ has m clauses and n variables. Then we realize that Gφ will
have m clusters.
First observation is
1 Any independent set must have at most one vertex from a cluster.
2 This means that the largest independent set is of size ≤ m.
Second observation is
1 If xi in one cluster belongs to an independent set then no xi
belongs to the independent set.
2 If xi in one cluster belongs to an independent set then no xi
belongs to the independent set.
Thus we can think of the vertices in the independent set as variables
that are made true in that cluster.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 15 / 1
Independent Sets
This means if there is a independent set that contains m vertices it
must have one vertex from each cluster. Thus the corresponding
assignment must make the formula φ true.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 16 / 1
Independent Sets
On the other hand if we φ is satisfiable then the assignment satisfies
each clause. So, it satisfies one literal in each clause. We can pick all
these literals and get an independent set of size m.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 17 / 1
Independent Sets
Theorem
φ is satisfiable if and only if Gφ contains an independent set of size m.
Where m is the number of clauses in φ.
It is readily seen that Gφ can be computed in polynomial time. So this
shows that
3SAT ≤p IS
Thus IS is NP-complete.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 18 / 1
Independent Sets
Formally the reducibility is given by
1 Input hφi.
2 Let m be the number of clauses in φ.
3 Compute Gφ and output hGφ , mi.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 19 / 1
Independent Sets
We have so far seen that
SAT ≤p 3SAT ≤ IS
Is it true that
IS ≤p SAT ?
The answer is yes. This is a consequence of the Cook-Levin Theorem.
Therefore, all these problems are polynomial time reducible to each
other.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 20 / 1
Independent Sets
Now, I want to show you two easy reducibilities. The first one is almost
trivial.
Let us define another problem in graph theory.
Definition
Let G = (V , E) be a graph. C ⊆ V is called a clique all the vertices in I
have edges between them. Thus for all x, y ∈ I where x 6= y
{x, y } ∈ E.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 21 / 1
NP-completeness
The figure shows a graph on 10 vertices. a, b, f, g is a clique.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 22 / 1
NP-completeness
The figure shows a graph on 12 vertices. a, d, f is a clique.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 23 / 1
NP-completeness
The figure shows a graph on 12 vertices. b, c, d, j,k is a clique.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 24 / 1
Clique
Let us define the following language:
CLIQUE = {hG, k i : G has an clique of size k }.
So computationally we have a problem in which we will be given:
1 A graph G.
2 and an integer k .
We have to find out if G has a clique of size k .
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 25 / 1
Clique
It is very easy to see that
CLIQUE ∈ NP.
Again this is your homework.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 26 / 1
Clique
We want to show that CLIQUE is NP-complete.
We have three problems that we know are NP-complete.
1 SAT
2 3SAT
3 IS.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 27 / 1
Clique
We can show any one of the following to establish the
NP-completeness of CLIQUE.
1 SAT ≤p CLIQUE
2 3SAT ≤p CLIQUE
3 IS ≤p CLIQUE
Which one should we choose. The answer is the one that is the
easiest. There is no need to do more work than required. In this case,
we should choose the last one because both the problems seem to be
closely related.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 28 / 1
Clique
So what is the relation between independent sets and cliques? The
answer is that it is very simple. Let G = (V , E) be a graph. Let us
define the complement of a graph G = (V , E 0 ) where
E 0 = {{x, y } : {x, y } 6∈ E}.
So G contains all edges that are not in G.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 29 / 1
Clique
Put figure. Here is a graph G and its complement.
The figure is more clear if we put both the graphs together in different
colors. G is in red and G is in blue.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 30 / 1
Clique
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 31 / 1
Clique
Let us now revise the definitions of independent set and clique.
1 I is an independent set if for all x, y ∈ I with x 6= y , {x, y } 6∈ E.
2 C is a clique if for all x, y ∈ I with x 6= y , {x, y } ∈ E.
Thus we observe that I is an independent set in G if and only if I is a
clique in G!
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 32 / 1
Clique
Now the reducibility is easy to come up with:
1 On input hG, k i
2 Output hG, k i
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 33 / 1
Clique
Theorem
IS ≤p CLIQUE
Consequently CLIQUE is also NP-complete.
How do we prove this. We have to give a reducibility. The reducibility
takes a pair hG, k i and outputs hG, k i. Clearly,
G has an independent set of size k if and only if G has a clique of size k .
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 34 / 1
Vertex Cover
Let us define another problem in graph theory.
Definition
Let G = (V , E) be a graph. W ⊆ V is called a vertex cover if all edges
intersect W . Thus for all x, y ∈ E
{x, y } ∩ W 6= ∅.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 35 / 1
Vertex Cover
The figure shows a graph on 10 vertices. b, c, f is a vertex cover.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 36 / 1
Vertex Cover
The figure shows a graph on 12 vertices. a, c, d, f is a vertex cover.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 37 / 1
Vertex Cover
Let us define the following language:
VC = {hG, r i : G has an clique of size r }.
So computationally we have a problem in which we will be given:
1 A graph G.
2 and an integer r .
We have to find out if G has a vertex cover of size r .
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 38 / 1
Vertex Cover
It is very easy to see that
VC ∈ NP.
Again this is your homework.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 39 / 1
Vertex Cover
We want to show that VC is NP-complete.
We have three problems that we know are NP-complete.
1 SAT
2 3SAT
3 IS.
4 CLIQUE
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 40 / 1
Vertex Cover
We can show any one of the following to establish the
NP-completeness of CLIQUE.
1 SAT ≤p VC
2 3SAT ≤p VC
3 IS ≤p VC
4 CLIQUE ≤p VC
Once again, we will choose the one where the reducibility is very easy
to come up with!
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 41 / 1
Vertex Cover
If we think about vertex cover and independent sets there is a nice
relationship between them. Let G = (V , E) be a graph. Let us take W
to be a vertex cover. Let us think about the complement of the vertex
cover. We know that W is a vertex cover. It’s complement is
X = V \ W . Thus for every edge {x, y } ∈ E we have
{x, y } ∩ W 6= ∅.
But this is the same as saying
{x, y } 6⊆ X .
Thus no edge is present in X . So, what is X then?
It is an independent set.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 42 / 1
Vertex Cover
Theorem
W is a vertex cover of G if and only if X = V \ W is an independent set
of G.
Theorem
G contains an independent set of size k if and only if it contains a
vertex cover of size n − k where n is the number of vertices in G.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 43 / 1
Vertex Cover
Here is a graph G and with an independent set in it. The remaining
vertices make a vertex cover.
The figure is more clear if we separate out the independent set from
the rest of the vertices.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 44 / 1
Vertex Cover
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 45 / 1
Vertex Cover
Now the reducibility is easy to come up with:
1 On input hG, k i
2 Output hG, n − k i where n is the number of vertices in G.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 46 / 1
Vertex Cover
Theorem
IS ≤p VC
Consequently VC is also NP-complete.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 47 / 1
Vertex Cover
Here is a list of the NP-complete problems we have so far.
1 SAT (Cook-Levin)
2 3SAT (By reducing SAT to 3SAT)
3 IS ( By reducing 3SAT TO IS)
4 CLIQUE (BY reducing IS to CLIQUE)
5 VC (BY reducing IS to VC).
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 48 / 1
Hamiltonian Paths
Now, we will look at another problem and prove that it is NP-complete.
This reducibility is not going to be so easy. Let us define the problem
first.
Let G = (V , E) be a directed graph. Thus edges are ordered pairs and
they have a direction. Here is a picture of a directed graph for you. Let
us define a hamiltonian path in this graph.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 49 / 1
Hamiltonian Paths
A hamiltonian path from a s to t is a path in the graph:
1 It starts at s and ends at t.
2 It contains all the vertices of the graph exactly once.
Sarmad Abbasi (Virtual University) Theory of Computation December 17, 2007 50 / 1
