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

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.

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:

advertisement
advertisement

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

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.

Participate in C++ Programming Certification Contest of the Month Now!

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.

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

advertisement
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
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.