C++ Program to Check Whether a Vertex Cover of Size k Exists or Not

This is a C++ Program To Check Whether A Vertex Cover Of Size K exists For A Given Graph

The problem takes E edges as input and outputs whehter vertex cover of size K of the graph exists or not.

Vertex Cover of a Graph is, 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}.
Here minimal vertex cover size is 2. So a vertex cover of size 1 does not exist, rest all sizes exist.

Example:

Some of the possible vertex covers are: {1,2,4,7} or {1,3,5,6} and many more.
Here minimum possible vertex cover size is 3, so size 1 and 2 vertex covers won’t exist.

Size of vertex cover, is the cardinality of the vertex cover. Generate all possible subsets of size K, and check whether it covers all edges or not.

1. Derive an adjacency matrix from the graph.
2. Using Gosper’s Hack, generate all subsets.
3. Mark all edges, connected with the vertices in generated subset.
4. Increment the count on visiting new edge.
5. If the final count is equal to edges, then vertex cover is possible.
6. Else, generate new subset, until all subsets are exhausted.
7. If no vertex cover, exist then we do not have a vertex cover of size K.

Here is source code of the C++ Program to check Vertex Cover of size 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;
 
bool graph[1001][1001];
bool vis[1001][1001];
 
int i,j,k,v;
int n,e,x,y;
 
bool isVertexCover(int sz)
{
    int c,r,cnt=0;
    int set = (1 << sz) - 1;
    int limit = (1 << n);
    while (set < limit)
    {
        memset(vis,0,sizeof(vis));
        cnt = 0;
        for (j = 1, v = 1 ; j < limit ; j = j << 1, v++)
        {
            if (set & j)
            {
                for (k = 0 ; k <= n-1 ; k++)
                {
                    if (graph[v][k] && !vis[v][k])
                    {
                        vis[v][k] = 1;
                        vis[k][v] = 1;
                        cnt++;
                    }
                }
            }
        }
        if (cnt == e)
            return true;
        c = set & -set;
        r = set + c;
        set = (((r^set) >> 2) / c) | r;
    }
    return false;
}
 
int main()
{
	cout<<"Enter number of vertices:";
	cin>>n;
	cout<<"\nEnter number of Edges:";
	cin>>e;
	for(i=0;i<e;i++)
	{
		cout<<"Enter the end-points of edge "<<i+1<<":";
		cin>>x>>y;
		x--; y--;
		graph[x][y]=1;
		graph[y][x]=1;
	}
	cout<<"Enter the size of Vertex Cover to check for (should be less than number of vertices) :";
	cin>>k;
	if(isVertexCover(k))
	cout<<"Vertex Cover of size"<<" "<<k<<" exist.\n";
	else
	cout<<"Vertex Cover of size"<<" "<<k<<" does not exist.\n";
	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 matrix.
4. Then we check the possibility of a vertex using function “isVertexCover()”.

 
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:2 3
Enter the end-points of edge 3:3 4
Enter the end-points of edge 4:1 4
Enter the size of Vertex Cover to check for:1
Vertex Cover of size 1 does not exist.
 
Case 2:
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:2 3
Enter the end-points of edge 3:3 4
Enter the end-points of edge 4:4 1
Enter the size of Vertex Cover to check for:3
Vertex Cover of size 3 exist.
 
Case 3:
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:2 3
Enter the end-points of edge 3:3 4
Enter the end-points of edge 4:1 4
Enter the size of Vertex Cover to check for:2
Vertex Cover of size 2 exist.

Sanfoundry Global Education & Learning Series – C++ Algorithms.
To practice all C++ Algorithms, here is complete set of 1000 C++ Algorithms.