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

**Program:**

#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;

}

**Output:**

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.

## No comments:

## Post a Comment