Part VI. Vertex Cover Problem
10 Vertex Cover Problem
Vertex Cover
A vertex cover of a graph is a set of vertices, V such that if (a, b) is an edge of a graph, then a or b or both must be present in V.
Consider the following graph:
In the above graph, vertex cover is {z, w}.
Let V= {z, w}
The edges of the above graph are uw, vw, xw, vz, yz. Note that in every edge, at least one vertex is a member of V.
For example,
Consider the edge uw. Here, vertex w ∈ V.
Consider the edge vz. Here, vertex z ∈ V.
Thus, {z, w} form a vertex cover.
Vertex Cover Problem
The vertex cover problem is to check whether a graph has a vertex cover of size k.
Vertex Cover Problem is NPComplete
We know that a problem is in class NPComplete if: it is in NP and it is NP Hard.
Theorem:
Vertex cover problem is NPcomplete.
Proof:
Step 1: Prove that vertex cover problem is in class NP.
A set with n elements has 2^{n} possible subsets. Then a graph with n vertices has 2^{n} possible subsets of vertices. So an algorithm needs to check whether any one of these subsets form a vertex cover. It has worst case time complexity Θ(2^{n}). (not polynomial time, but exponential time). Let we are given a graph and a ’certificate’ telling that a subset of vertices form a vertex cover. An algorithm can verify whether at leat one vertex of every edge in the graph is an element of this vertex cover in polynomial time.
So vertex cover problem is in class NP.
Step 2: Prove that vertex cover problem is NPhard.
We know that a problem is NPHard, if every problem in NP can be reduced to this problem in polynomial time. The approach we used is as follows: In the previous section, we already proved that all NP problems can be reduced to SAT. Then, again we found that SAT problem can be reduced to 3CNFSAT problem. Again, we reduced 3CNFSAT problem to clique problem. Then, if we can reduce clique problem to vertex cover problem in polynomial time, we can say that vertex cover problem is NPhard.
We need to reduce clique problem to vertex cover problem.
Consider the following graph with clique {u, v, x, y}.
Take the complement of the above graph, G. That is G.G is
For the graph vertex cover is {z,w}.
This vertex cover is found by V  V’.
That is, {u,v,w,x,y,z}  {u,v,x,y} = {z,w}
So from the clique, we can find out the vertex cover of a graph using the above mechanism.
Thus the given clique problem is reduced to vertex cover problem. This means vertex cover problem is NPhard.
In step 1, we proved that vertex cover problem is in NP.
In step 2, we proved that vertex cover problem is NPhard.
So, vertex cover problem is an NPcomplete problem.
18 videos56 docs44 tests

1. What is the Vertex Cover Problem in Computer Science Engineering (CSE)? 
2. How is the Vertex Cover Problem relevant to Computer Science Engineering (CSE) exams? 
3. What are the applications of the Vertex Cover Problem in CSE? 
4. What are the common algorithms used to solve the Vertex Cover Problem in CSE? 
5. Can the Vertex Cover Problem be solved in polynomial time? 
18 videos56 docs44 tests


Explore Courses for Computer Science Engineering (CSE) exam
