Vertex Cover Problem | Theory of Computation - Computer Science Engineering (CSE) PDF Download

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 NP-Complete
We know that a problem is in class NP-Complete if: it is in NP and it is NP Hard.

Theorem:
Vertex cover problem is NP-complete.

Proof:

Step 1: Prove that vertex cover problem is in class NP.
A set with n elements has 2ⁿ possible subsets. Then a graph with n vertices has 2ⁿ 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ⁿ). (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 NP-hard.
We know that a problem is NP-Hard, 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 3-CNF-SAT problem. Again, we reduced 3-CNF-SAT 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 NP-hard.

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 NP-hard.

In step 1, we proved that vertex cover problem is in NP.
In step 2, we proved that vertex cover problem is NP-hard.
So, vertex cover problem is an NP-complete problem.