## 📜Introduction

Before learning to find the minimum vertex cover size, let us first see what a vertex cover is.

A vertex cover is a subset of vertices in the graph on which every other node present in the graph is incident. A vertex cover in an undirected graph is a subset of nodes where every node (u,v) of the graph is in its vertex cover.

Now the problem arises there can be many vertexes covered in a graph, and how to find the minimum one? Before calculating the minimum vertex cover size, let us first see some cover examples for a clear understanding.

## 💡Example

For the below example, find the minimum vertex cover size.

We can see that the minimum vertex cover size is 2. (1,2) or (1,3) are the possible subset as all the nodes are incident on them. So the minimum vertex cover size is 2.

Now let’s move to the algorithmic part to find the minimum vertex cover size.

## 📜Naive Approach

A naive approach can generate all the subsets of all vertices(2^V). Now for each current subset:

👉Count the nodes that can be visited from the vertices of the current subset.

👉If the edges covered are equal to the total number of the edges present, return the current subset.

👉The time complexity for the brute force is O((V+E)*2^V). 2^V to generate all the subsets and (V+E) to traverse all the edges.

👉We can use a binary search to improve the time complexity to obtain better results.

## 📜Optimal Approach

We first generate all the subsets(2^V). The 2^V subsets can be broken down into its components like (VCv + VCv-1 + VCv-2 +.......VCk +......VC0). We aim to find the value of minimum k possible such that a subset of size k is in our vertex cover. So, according to our calculation, the subset of size more than k will also be in our vertex cover,i.e., k,k+1, k+2, k+3, and so on up to n.

Now let’s assume a boolean array of size n and call it CoverVertex[]. So if the vertex cover of size x exists, we put a ‘1’ at the xth position; otherwise, ‘0’. The array CoverVertex[] will look like this:

```
Pos: 1 2 3 4 5 6….k k+1…..n
Value: 0 0 0 0 0 0 ….1 1 ……1.
```

As the array is sorted, we can apply search, as no index before k has a value of 1, and every index after k(inclusive) will have a value of 1, so k is our answer. Now the problem is how to generate all subsets of a given size. The idea is to use Gosper’s hack.

### 🤔Gosper’s Hack

It is a method to generate the next number with the same amount of bits set. To generate the next number, we set the first x bits starting from the right and continue till the number is less than 2^V. This allows us to produce all VCx numbers with the x bits set.

Gosper’s hack works well for V = 31 only. If we take ‘long long int’, it can work up to V = 63.

#### 🧑💻Pseudo Code

```
int set = (1 << k) - 1;
int bound = (1 << V);
while (set < bound)
{
// Do your computation with the current Set
solve(set);
// Gosper's hack:
int l = set & -set;
int r = set + l;
set = (((r^set) >>> 2) / l) | r;
}
```

We use Gosper's hack to generate all subsets of size x,i.e., to check whether we have a zero or one at any index x in CoverVertex[] array.

## Code🧑💻

```
#include<bits/stdc++.h>
#define maxn 25
using namespace std;
/* Global array to store the graph */
bool graph[maxn][maxn];
bool isCover(int V, int k, int E)
{
/* Set has first 'k' bits set initially */
int set = (1 << k) - 1;
int bound = (1 << V);
bool visited[maxn][maxn];
while (set < bound)
{
/* Reset the visited array for every subset
of vertices.*/
memset(visited, 0, sizeof vis);
/*Set counter for number of edges covered
from this subset of vertices to zero.*/
int c = 0;
/* selected vertex cover is the indices
where 'set' has it's bit high.*/
for (int j = 1, v = 1 ; j < bound ; j = j << 1, v++)
{
if (set & j)
{
/* Mark all edges emerging out of this
vertex visited.*/
for (int k = 1 ; k <= V ; k++)
{
if (graph[v][k] && !visited[v][k])
{
visited[v][k] = 1;
visited[k][v] = 1;
c++;
}
}
}
}
if (c == E)
return true;
/* Generate the previous combination with k bits high
set & -set = (1 << last bit high in set).*/
int x = set & -set;
int r = set + x;
set = (((r^set) >> 2) / x) | r;
}
return false;
}
int findMinCoverK(int n, int m)
{
/* Binary search the answer */
int left = 1, right = n;
while (right > left)
{
int mid = (left + right) >> 1;
if (CoverVertex(n, mid, m) == false)
left = mid + 1;
else
right = mid;
}
return left;
}
void insertEdge(int u, int v)
{
gr[u][v] = 1;
gr[v][u] = 1;
}
// Driver code
int main()
{
memset(gr, 0, sizeof gr);
int V = 6, E = 7;
insertEdge(1, 2);
insertEdge(1, 3);
insertEdge(2, 3);
insertEdge(2, 4);
insertEdge(3, 5);
insertEdge(4, 5);
insertEdge(4, 6);
cout << "Minimum size of a vertex cover = "
<< findMinCoverK(V, E) << endl;
return 0;
}
```

### 📚Output

`Minimum size of a vertex cover = 3`

### ⏳Time complexity

The time complexity for the optimal approach is O(E+VCv/2+ VCv/4 +....up to VCk).

## Frequently Asked Questions

### What's wrong with vertex cover, exactly?

The vertex cover problem is NP-Complete unless P = NP is established. There is no known polynomial-time method for determining the least vertex cover of a graph. However, it is possible to find a graph's vertex cover using approximate algorithms that run in polynomial time.

### What vertex cover is the smallest?

A minimum vertex cover has the fewest vertices possible for a particular graph. The Wolfram Language function FindVertexCover[g] can be used to determine a graph's minimal vertex cover.

### Does NP have minimum vertex cover?

Every minimal vertex cover is a minimal vertex cover, but not necessarily the other way around (that is, a vertex cover that is not a suitable subset of any other cover). An NP-complete task is locating the smallest vertex cover of a generic graph.

### What distinguishes a vertex cover from a dominant set?

The degree zero vertexes are not close to the vertex cover, even though they " cover " all the edges. A dominating set might not be a vertex cover if there is an edge, such as e = (u,v), where u and v are both outside the dominating Set.

### What makes NP different from NP-hard?

The Set of NP-hard problems is solved in polynomial time by non-deterministic machines and is difficult to locate but simple to prove.

## Conclusion

In this article, we learned how to calculate the minimum vertex cover size with the help of a code, and through the learning, we came to different new concepts. That’s all from the article. I hope you all like this article.

**Recommended problems -**

If you want to learn more, check out our articles on __Construct the Full K-ary Tree from its Preorder Traversal__, __Regular and Bipartite graphs__, __What Is Web2Py?__, __Why To Use Web2py?__, __Postbacks and Internationalization in web2py__, __Third Party Modules In Web2py__, __Tasks In Web2py__, and __XML in Web2py__.

**Happy Coding!**