Introduction
The vertex cover problem is an NPComplete problem. An NPComplete problem is a problem that cannot be solved in polynomial time. So to solve the vertex cover problem we will be using an approximate method to get the nearoptimal solution.
In this blog, we will discuss the NPComplete problem known as the Vertex cover problem. We will be solving the problem using an approximation method to get the nearoptimal solution.
Problem Statement
In the vertex cover problem, you will be given an undirected graph G, your task is to find the Minimum vertex cover.
Vertex Cover
An undirected graph's vertex cover is a subset of its vertices that includes either "u" or "v" for each of the graph's edges (u, v).
For example:
The vertex cover for the above graph can be: {0, 1, 2}, {1, 3, 4} as all of the edges available in the graph are adjacent to these vertices. But we have to find the minimum size vertex cover that is why for the above graph the minimum vertex cover is {1, 2}. Also all of the edges are adjacent to vertex 1 and vertex 2.
Another Example,
Sample Examples
Input
Output
Vertex cover: 0 3 4 6
Explanation
We are basically selecting any random edge (u, v) then for that edge either u or v is in the output.
For example,
And the optimal vertex cover for the above input graph will be 0, 3, 4, 6 (there can be multiple answers also, but the minimum size will remain the same) because all of the edges available in the graph are adjacent to these vertices as shown in the below figure.
Approximate Solution
The vertex cover problem is an NPComplete problem and it has been proven that the NPComplete problem cannot be solved in polynomial time. So, we try to find the near optimal solution that finds a vertex cover.
The approach mentioned below finds the vertex cover whose size is guaranteed to be no more than twice the size of an optimal vertex cover.
Approach to solve the problem
 Initialize an empty set C to store the result
 Consider a collection E of all the edges in a graph.

While E is not empty:
 Pick an edge from collection E.
 Add u and v of the picked edge and store it in result set C.
 Remove all of the edges that incident on either u or v
 Print result
Pseudo Code
SOLVE(){
bool visited[total_vertices] < {false, false, ......., false}
for u < 0 to total_vertices:
if visited[u] is false:
for v < vertices[u]:
if visited[v] is false:
visited[v] = visited[u] < false
break;
for i < 0 to total_vertices:
if visited[i] is true:
print i
}
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// graph class
class undirected_graph{
public:
// adj list
vector<int> *vertices;
int total_vertices;
// constructor
undirected_graph(int number_of_vertices){
total_vertices = number_of_vertices;
vertices = new vector<int>[number_of_vertices];
}
// function to add edge in our graph
void addEdge(int v, int w){
vertices[v].push_back(w);
vertices[w].push_back(v);
}
// solving vertex cover problem
void solve(){
// visited boolean array
vector<bool> visited(total_vertices, false);
// visiting all of the vertices one by one
for(int u = 0; u < total_vertices; u++){
// if current vertex is not visited
// process it
if(!visited[u]){
// visiting all of the vertices from 'u'
for(int v : vertices[u]){
// if it's not already visited
// mark it as visited and break the loop
if(!visited[v]){
visited[u] = visited[v] = true;
break;
}
}
}
}
// printing vertex cover
for(int i = 0; i < total_vertices; i++){
if(visited[i]) cout << i << " ";
}
}
};
int main(){
// creating graph
undirected_graph G(7);
G.addEdge(0, 1);
G.addEdge(1, 3);
G.addEdge(3, 4);
G.addEdge(4, 5);
G.addEdge(4, 6);
G.addEdge(5, 6);
G.addEdge(6, 2);
G.addEdge(2, 0);
// calling the function for vertex cover problem
cout << "Vertex cover: ";
G.solve();
return 0;
}
Output
Vertex Cover: 0 1 2 3 4 6
Time Complexity
The Time Complexity of the above algorithm is O(V + E), where V is the number of vertices and E is the number of edges in our graph.
Space Complexity
The Space Complexity of the above algorithm is O(V), where V is the number of vertices. As we are using a boolean array to keep the record of already visited vertices.
Read More  Time Complexity of Sorting Algorithms