The document Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.

All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

**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^{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 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.

Offer running on EduRev: __Apply code STAYHOME200__ to get INR 200 off on our premium plan EduRev Infinity!

36 videos|39 docs|39 tests