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

«
»

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

Problem Description

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.

advertisement

Example:
cpp-program-check-bipartite-graph

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:

cpp-program-check-vertex-cover-size-k-exists

advertisement

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.

Problem Solution

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.

Program/Source Code

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.

advertisement
#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;
}
Program Explanation

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()”.

Runtime Test Cases
 
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.

advertisement

advertisement
advertisement
advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn