Problem Statement
Our problem statement is to find the minimum vertex cover.
First to find the minimum vertex cover, we are going to prove that vertex cover is np complete
problem and then np-hard.
For np-complete,the first step is
1) Is vertex cover a decision problem.
2) Given a vertex cover of G
3) let count be an integer
4) set count to 0
5) for each vertex v in V’
6) remove all edges adjacent to v from set E
7) increment count by 1
8) if count = k and E is empty
9) then
10) the given solution is correct
11) else
12) the given solution is wrong
13)
Logical Proof:
Step 1: Vertex Cover is in NP
Given a set of vertices, we can verify if it's a vertex cover by checking each edge in the
graph and ensuring that at least one endpoint of each edge is included in the proposed
set of vertices. Since the number of edges is polynomial in terms of the size of the
input, this verification can be done in polynomial time. Therefore, Vertex Cover is in NP.
Step 2: Vertex Cover is NP-hard
To prove NP-hardness, we'll reduce a known NP-complete problem, such as the Clique
Problem, to Vertex Cover.
Clique Problem:
Given an undirected graph G and an integer k, determine whether there exists a clique of
size k in G.
Reduction:
We'll show that we can transform any instance of the Clique Problem into an instance of
the Vertex Cover Problem in polynomial time.
Given a graph G=(V,E) and an integer k, determine if there exists a clique of size k in
G.
Reduction: Let G=(V,E) be an instance of the Clique [Link] a new graph
G=(V′,E′) as follows:
● V’=V ∪E (i.e., each edge in G becomes a vertex in G’’
● E′ contains all possible edges between vertices in′V, except for the edges
that were in E.
● Claim:G has a clique of size k if and only if G has a vertex cover of size
∣V∣+∣E∣−k.
Proof of Claim: Suppose G’ has a clique of size k. Then, in G’ , select all vertices
corresponding to this clique and none of the other vertices. This set of vertices covers
all edges in G’ except for the edges between the chosen vertices. Since the size of the
clique is k, the size of the vertex cover in G’ is ∣V∣+∣E∣−k.
Conversely, suppose G has a vertex cover of size ∣V∣+∣E∣−k. Then, in G’ , there must
be at least ∣V∣−k vertices from V and |E|−(∣V∣−k)= ∣E∣+k−∣V∣ vertices from V and E.
Since each edge in G’ is incident to exactly one vertex in V and one vertex in E, these
∣V∣−k vertices from V must form a clique of size k in G’.
This reduction can be done in polynomial time, and thus, Vertex Cover is NP-hard.
good morning students into this lecture
00:00:05under this NP harden and be complete I
00:00:08will tell you about the what Xcover
00:00:10problem and I will show that vertex
00:00:13cover is also and be complete problem in
00:00:18our previous lecture we have covered all
00:00:21these problem sake says CNF side 3sat
00:00:25and then I had a reduced clique problem
00:00:28from this CNS at now in this lecture I
00:00:32will prove that this is np-complete and
00:00:35for that I introduced glede problem to
00:00:38vertex cover problem
00:00:40so our first this is just the revision
00:00:45of what we have done previously that
00:00:47what is the clique problem I will just
00:00:49tell you that it was a clique suppose if
00:00:53this graph is given to you we need to
00:00:55find out is there any sub graph of this
00:00:58graph that is complete yes like this 1 2
00:01:013 4 this is the sub graph of this graph
00:01:04and that is a complete graph complete
00:01:07means every node is connected to every
00:01:10other node so this graph is having a
00:01:13clique of size oh and what was the clear
00:01:16decision problem late decision problems
00:01:19past that suppose if a graph is given to
00:01:22you you need to find out is it having a
00:01:25clique of size K if it is yes then you
00:01:29can say it is having a clique of size k
00:01:31otherwise not so this was the clique
00:01:34problem now first I will tell you that
00:01:38what is the vertex cover problem and
00:01:41then I will reduce the cleat to vertex
00:01:45cover problem so first thing is that
00:01:47what is what do you mean by vertex cover
00:01:50of a graph okay now suppose this graph
00:01:54is given to you we need to find out the
00:01:56vertex cover
00:01:57now what X cover means you need to find
00:02:00out those vertices that cover all the
00:02:04edges of your graph that means that
00:02:07touch every edge in your graph suppose
00:02:11like here this
00:02:13is given to you and suppose if I am
00:02:15taking the vertices to five and four
00:02:18we'll see whether these vertices cover
00:02:21all the edges of your graph okay for
00:02:25this pose I'm first taking two I'm
00:02:29taking this to vertex
00:02:31okay now what are the different edges
00:02:34that are like that are starting from
00:02:38this two node so they said I'm cutting
00:02:41this one I'm cutting this one and I will
00:02:45cut this one so this to mode is covering
00:02:48like you can say it is covering these
00:02:51three edges okay next you take the node
00:02:54number five I suppose I'm taking this
00:02:57one now now again cut all the edges that
00:03:00are touching five node okay which IJ's
00:03:03are there this five one five three and
00:03:07five four okay
00:03:10so these two vertices two and five will
00:03:13touch all these or you can say will
00:03:17cover these six edges but still one edge
00:03:20is more for that I need to take either
00:03:23three node or the fourth node suppose I
00:03:26have taken the fourth node so you can
00:03:28see this is also going to cover this
00:03:31edge is there any remaining edge over
00:03:33here no so you can see these three
00:03:37vertices are covering all the edges of
00:03:40our graph so that is the vertex cover of
00:03:44a graph BC okay so now what is the
00:03:48definition of this a vertex cover of a
00:03:51graph G is equal to V E is a subset VC
00:03:56so this a vertex cover that is a subset
00:04:00of V what is V V contains all the
00:04:03vertices 1 2 3 4 5 so it should be
00:04:06firstly a subset of this such that if a
00:04:09B belongs to e like if ap like if 1 2 is
00:04:15an edge 1 2 belongs to e then either a
00:04:18should belong to this VC or B should
00:04:22belong to PC or it can be both suppose I
00:04:25am taking 2 4
00:04:27- one first soto one is an edge a piece
00:04:31an edge that belongs to you yes one two
00:04:33is an edge then either one should belong
00:04:36to VC but here one is not there or two
00:04:40should belong to VC yes two is here okay
00:04:43or you take this two for edge
00:04:46- four is an edge over here yes then
00:04:49either two should belong to this VC yes
00:04:522 is here
00:04:53all four should belong to this or both
00:04:55so actually here both 2 as well as four
00:05:00are here so that is the definition of
00:05:02your vertex cover now what is the size
00:05:05of the vertex cover over here there is a
00:05:08vertex cover of size 3 okay so or what
00:05:12is this in VC will cover all the edges
00:05:15of G now we have to prove that vertex
00:05:19cover is np-complete problem now in
00:05:22order to prove that any problem is
00:05:24np-complete what was the first condition
00:05:27we need to find out that is it a
00:05:29decision problem that means like we need
00:05:34to put this problem in such a way that
00:05:37the output of that should be either yes
00:05:39or no like here I have written over here
00:05:42like you can say suppose a graph is
00:05:45given to you you can ask the question is
00:05:48there any vertex cover of size k if
00:05:52answer is yes then it is having that
00:05:54vertex cover otherwise answer would be
00:05:56no like for this graph I can say I can
00:05:59ask you is there any vertex cover of
00:06:01size - no is there any vertex cover of
00:06:06size 3 yes okay so what takes cover
00:06:10takes a graph G and integer K as input
00:06:12and ask is there any vertex cover of G
00:06:15which contains K vertices or not if it
00:06:18is their answer would be yes otherwise
00:06:21answer would be no so this is the
00:06:25definition of vertex cover and according
00:06:28to the first condition I have shown you
00:06:31that vertex cover is a decision problem
00:06:36okay the next condition that we need to
00:06:39show is that vertex cover should P and P
00:06:42problem now again what is an P and P
00:06:45means is there any non-deterministic
00:06:48algorithm that can be solved in
00:06:50polynomial time
00:06:51okay for that I have written this
00:06:54non-deterministic algorithm like you can
00:06:57say it can be solved in polynomial time
00:06:59now given we see the vertex cover of G
00:07:02for each vertex that belongs to BC if we
00:07:06move all the incident edges like here
00:07:10what we have done previously but they
00:07:14are saying like suppose a vertex cover
00:07:17is given to you two five four okay now
00:07:21for each vertex that belongs to VC cut
00:07:24all the incident edges okay
00:07:27so again I'm taking this for vertex
00:07:32cover to cut all the incident edges that
00:07:35is cut this cut this one and cut this
00:07:38one that are starting from two then four
00:07:40five cut all the incident edges this
00:07:43this and this one four four cut all the
00:07:47incident edges this one then you will
00:07:50check is there any remaining edge in the
00:07:52graph is there any remaining edge no
00:07:55okay if it is no that means it is having
00:07:59a vertex cover of size K but suppose if
00:08:03there is any remaining edge then it is
00:08:05not having any vertex cover of size K
00:08:09now this can be done in polynomial time
00:08:15okay why because your non-deterministic
00:08:18algorithm would take all these vertices
00:08:22in parallel and it will cut all the
00:08:25incident edges in parallel okay so this
00:08:28problem can be solved in polynomial time
00:08:31but by using non-deterministic algorithm
00:08:34okay so again I am repeating for each
00:08:37vertex that belongs to VC remove all the
00:08:40incident edges check if all the edges
00:08:42are removed yes like in our case it was
00:08:45removed so you can say that it is having
00:08:48about X cover of
00:08:49ski now this problem can be solved in
00:08:53Big O of number of edges plus number of
00:08:56vertices okay so it is polynomial in
00:09:00time so this vertex cover belongs to NP
00:09:03that means this problem is in NP now the
00:09:08third one that is like it will be
00:09:11difficult one like we have to show that
00:09:13vertex cover is an big hard problem so
00:09:18in order to show that what X cover is
00:09:20and be hard we need to reduce our
00:09:23problem that is already proved to be and
00:09:26be hard and we will reduce that to
00:09:29vertex cover now here what I have taken
00:09:33I have taken a clique problem
00:09:36okay now that clique problem will be
00:09:39reduced to vertex cover problem in
00:09:41polynomial time if I am able to do this
00:09:44thing then I can say that the vertex
00:09:47cover is and be hard as I have already
00:09:50shown you that clique problem is np-hard
00:09:53problem okay for that I need to take a
00:09:58graph g ve suppose here I am giving a
00:10:02graph G and I am giving the key as the
00:10:05input that means I am saying that graph
00:10:07is having a clique of size K so that is
00:10:11the input that I am taking okay now that
00:10:16graph will be having a maximum clique of
00:10:20size K if and only if now here I have
00:10:23written G - if G - I will tell you what
00:10:26is that J - is a complement of this
00:10:29graph G if and only if the graph G - has
00:10:33a vertex cover of size number of
00:10:36vertices - Greek that means if G - is
00:10:41having a vertex cover of size this then
00:10:44only your input graph will be having a
00:10:47clique of size K otherwise it is not
00:10:50possible so if I am able to reduce this
00:10:55problem to this I need to show this
00:10:57thing so first thing is that I will tell
00:11:00you that what is G - that Muskaan
00:11:03element of a graph now here you take
00:11:06this graph in which you are having one
00:11:08two three four five vertices so G is V E
00:11:11is these edges 1 2 3 4 5 6 & 7 IG Sathya
00:11:17now what would be the complement of this
00:11:20complement of this graph is this that
00:11:23means you assume that this graph is your
00:11:27complete graph okay
00:11:29let me make this thing okay now if you
00:11:34want this graph to be complete graph
00:11:36there should be an edge from 1 to 5 from
00:11:411 to 2 and from 1 to 4 because in a
00:11:46complete graph you should have an edge
00:11:48between all the nodes so there was no
00:11:51edge between 5 & 1 5 & 2 5 & 4 so I have
00:11:55made these so you just consider these
00:11:57red lines and make this graph again by 1
00:12:015 25 4 so that is the complement G dash
00:12:05in that vertices are same be set of
00:12:09vertices is same but II dash is what
00:12:11that is v 1 v 2 & 5 4 but here the e was
00:12:171 2 1 3 3 4 4 2 all these edges and 3 5
00:12:23so if you will combine this graph and
00:12:26this graph means without these red lines
00:12:29the previous graph original graph and
00:12:31this graph you will be getting this
00:12:33graph so what is that that is a complete
00:12:35graph actually okay so if you are
00:12:39merging the graph G & G dash you're
00:12:43getting a graph that is a complete
00:12:45similar to this one okay so this is the
00:12:50complement of a graph G dash so like
00:12:55what was our problem our problem was
00:12:57this is the input we are giving a graph
00:12:59G in which the number of vertices are n
00:13:03how many vertices are there file and
00:13:05click is K now what is the click of this
00:13:09what is a click again I am repeating
00:13:11click is a sub graph of this graph that
00:13:15is complete now
00:13:17this is the subgraph of this graph that
00:13:19is complete this sub graph that is
00:13:22complete one without this five one two
00:13:25three four so what is the size of the
00:13:27click over here click is full for this
00:13:30graph so you are giving a graph with
00:13:33clique of size K and I need to find out
00:13:38is G dash is having a vertex cover of
00:13:41size V minus k if it is possible then
00:13:45that means we have reduced this to this
00:13:48in polynomial time like you take this
00:13:52graph I have made cheap - okay now just
00:13:56find out that what is the vertex cover
00:13:58of this vertex cover means you need to
00:14:01find out the number of vertices that
00:14:04covering all the edges of this graph
00:14:06okay now what takes off cover of this
00:14:10graph is just five fine why because if I
00:14:15will take five five one will be cut five
00:14:19two will be cut and five four will be
00:14:21cut is there any more edge over here
00:14:23no so I can say the vertex cover of this
00:14:27is what five only five that means that
00:14:31is your one so what takes cover of this
00:14:36graph is given by a number of vertices
00:14:39that is file and - click - a clique size
00:14:43and what was the clique size of this
00:14:45graph ooh so 5 minus 4 is 1 so you are
00:14:48getting that so if you are giving a
00:14:51graph with number of vertices file and
00:14:54cleat size 4 then G Shaq a G - should
00:14:58have a vertex cover of size 5 - 4 1 so
00:15:01I'm able to get this thing so you can
00:15:04see that this problem is being reduced
00:15:07to vertex cover problem and one thing
00:15:11more here what is a vertex cover of this
00:15:14this is the size size of the vertex
00:15:17cover is V minus K but what is the
00:15:20vertex cover what X cover is given by
00:15:24this like you can write down what X
00:15:27cover is given by V - V -
00:15:30like for this graph what is the V V is
00:15:33set of vertices 1 2 3 4 5 and what is V
00:15:38- V - means like here what is the what
00:15:43assists that are in the fleek he - is
00:15:47that thing the vertices that belong to
00:15:50click like what is here click click was
00:15:531 2 3 4 so I can write down play keys 1
00:15:562 3 4 so if you will find out V - V -
00:16:00means P - V - that means you don't have
00:16:04to take those elements that are all but
00:16:07already present in V so I won't take 1 2
00:16:113 and 4 so what is remaining fine so you
00:16:14are getting 5 so you can see that the
00:16:17vertex cover of this is 5 size of this
00:16:21vertex cover is given by num
00:16:26what is this - key and the vertex cover
00:16:29like what Arthur said what is that set
00:16:33that is given by V - V - where V - is a
00:16:36set of vertices that belongs to fleek so
00:16:41here you can say that now I have shown
00:16:43you that vertex cover is our decision
00:16:46problem it is in NP and it is
00:16:49np-complete problem okay so it is
00:16:53np-hard so I can say it is np-complete
00:16:56problem so I have used this one clique
00:17:05problem to reduce this to vertex cover
00:17:08problem so this also I have added in
00:17:10this graph in this reduction graph and P
00:17:13reduction graph so again I am repeating
00:17:19what is a vertex cover problem if you
00:17:22have been given a graph G and an integer
00:17:25K you need to find out is there any
00:17:29vertex cover of size K if you are having
00:17:33the vertex cover of size K the output of
00:17:36this would be 1 otherwise it would be 0
Delete
IMPLEMENTATION
There are many approaches to solve vertex cover problem.
1) Approach using Approximation Algorithm
The approximation algorithm solve the vertex cover problem is a polynomial time algorithm. It is a
polynomial time 2 approximation algorithm.
Input: Graph G = (V, E), where V is the set of vertices and E is the set of edges.
Output: Approximate vertex cover C.
The steps required for the algorithm
1. Initialize an empty set C to store the vertex cover.
2. Create a copy E′ of the edge set E of the input graph G.
3. While ′E′ is not empty:
Select an arbitrary edge (u,v) from E′.
Add both vertices u and v to the vertex cover C.
Remove from E′ every edge incident on either u or v.
Algorithm
APPROX_VERTEX_COVER(G)
1. C ← {}
2. E' = E[G]
3. While E' is not empty:
4. Let (u, v) be an arbitrary edge of E'
5. C ← C ∪ {u, v}
6. Remove from E' every edge incident on either u or v
7. Return C
Input Parameters:
Input parameters include the graph (G), which consists of vertices and edges.
Time Complexity Analysis: The time complexity of the implementation is O(V+E), where V is the
number of vertices and E is the number of edges in the graph. This is because the algorithm iterates
over all edges once to select and add vertices to the vertex cover.
RESULT
Using approximation algorithm.
#include <iostream>
#include <vector>
using namespace std;
// Function to approximate the vertex cover
vector<int> ApproximationVertexCover(const vector<vector<int>>& graph) {
vector<int> vertexCover;
vector<vector<int>> edges = graph; // Copy of the edge set
while (![Link]()) {
// Select an arbitrary edge
int u = [Link]()[0];
int v = [Link]()[1];
edges.pop_back();
// Add vertices to the vertex cover
vertexCover.push_back(u);
vertexCover.push_back(v);
// Remove incident edges
for (auto it = [Link](); it != [Link]();) {
if ((*it)[0] == u || (*it)[1] == u || (*it)[0] == v || (*it)[1] == v) {
it = [Link](it);
} else {
++it;
}
}
return vertexCover;
// Example usage
int main() {
// Example graph
vector<vector<int>> graph = {{1, 2}, {2, 3}, {1, 3}, {3, 4}, {4, 5}};
// Finding approximate vertex cover
vector<int> vertexCover = ApproximationVertexCover(graph);
cout << "Approximate Vertex Cover:";
for (int vertex : vertexCover) {
cout << " " << vertex;
cout << endl;
return 0;