C++ Programming Code Examples C++ > Computer Graphics Code Examples C++ Program to Check Whether a Vertex Cover of Size k Exists 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 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. 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. 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. #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; }