Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev

Theory of Computation

Computer Science Engineering (CSE) : Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev

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:
Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev
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 2n possible subsets. Then a graph with n vertices has 2n 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 Θ(2n). (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.
Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev
We need to reduce clique problem to vertex cover problem.
Consider the following graph with clique {u, v, x, y}.
Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev
Take the complement of the above graph, G. That is G.G is
Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev
For the graph Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev 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!

Related Searches

Summary

,

video lectures

,

shortcuts and tricks

,

mock tests for examination

,

Exam

,

past year papers

,

Viva Questions

,

Previous Year Questions with Solutions

,

Free

,

MCQs

,

Sample Paper

,

Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev

,

Important questions

,

ppt

,

Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev

,

Vertex Cover Problem Computer Science Engineering (CSE) Notes | EduRev

,

Objective type Questions

,

study material

,

pdf

,

practice quizzes

,

Extra Questions

,

Semester Notes

;