C++ Program to Implement a Heuristic to Find the Vertex Cover of a Graph

This is a C++ Program To Implement Heuristic To Find A Vertex Cover Of A Given Graph.

The problem takes E edges as input and outputs vertex cover of the graph, implementing the following heuristic.

Vertex Cover of a Graph is to find, a set of vertices S, such that for every edge connecting A to B in graph, either A or B (or both) are present in S.

Example:

Possible Vertex Covers are: S = {1,2} or {1,3} or {1,4} or {2,3} or {2,4} or {3,4} or {1,2,3} or {1,2,4} or {2,3,4} or {1,3,4} or {1,2,3,4}.

Example:

There is no polynomial time algorithm invented up to date to find the minimum size vertex cover, though many approximate algorithms(heuristics) do exist. Here, implementation of one such heuristic is shown. Size of Vertex Cover obtained from this heuristic won’t be more than twice the size minimum vertex cover and can be prove using Discrete Mathematics (Graph Theory). Size of vertex cover, is the cardinality of the vertex cover.

1. Initialize a set S as empty.
2. Take an edge E of the graph connecting lets say, A and B.
3. Add both vertex to our set S.
4. Discard all edges in the graph with endpoints at A or B.
5. Go to step 2, if some edge is till left in the graph.
6. The final set S is a vertex cover of the graph.

Here is source code of the C++ Program to generate Vertex Cover for a given graph. The program is successfully compiled and tested under Linux platform. The program output is also shown below.

#include<bits/stdc++.h>
 
using namespace std;
 
vector<vector<int> > graph;
bool vis[100011];
int i,j; //variables for loop iteration
 
vector<int> solve_vertex(int n,int e)
{
	//we start visiting edges
	vector<int> S;
	for(i=0;i<n;i++)
	{
		if(!vis[i])
		{
			for(j=0;j<(int)graph[i].size();j++)
			{
				if(!vis[graph[i][j]]) //we only select those edges whose
								      //both vertices have not been visited yet!
				{
					vis[i]=true;
					vis[graph[i][j]]=true;
					break;
				}
			}
		}
	}
	for(i=0;i<n;i++)
		if(vis[i])
			S.push_back(i);
	return S;
}
int main()
{
	int n,e,x,y;
	cout<<"Enter number of vertices:";
	cin>>n;
	cout<<"Enter number of Edges:";
	cin>>e;
	graph.resize(n);
	memset(vis,0,sizeof(vis));
	for(i=0;i<e;i++)
	{
		cout<<"Enter the end-points of edge "<<i+1<<" : ";
		cin>>x>>y;
		x--; y--;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	vector<int> S = solve_vertex(n,e);
	cout<<"The required vertex cover is as follows:\n";
	for(i=0;i<(int)S.size();i++)
	cout<<S[i]+1<<" ";
	return 0;
}

1. User must first enter the number of vertices, N, and then number of edges, E, in the graph.
2. It should be followed by E lines, denoting A and B, if there is an edge between A and B.
3. The graph is stored as adjacency list.
4. Then the Heuristic is implemented, with our vector “S” as the final vertex cover using “solve_vertex()” function.

 
Case 1:
Enter number of vertices:4
Enter number of Edges:4
Enter the end-points of edge 1:1 2
Enter the end-points of edge 2:1 3
Enter the end-points of edge 3:4 3
Enter the end-points of edge 4:4 2
The required vertex cover is as follows:
1 2 3 4
 
Case 2:
Enter number of vertices:6
Enter number of Edges:3
Enter the end-points of edge 1:1 2
Enter the end-points of edge 2:2 3
Enter the end-points of edge 3:1 3
The required vertex cover is as follows:
1 2