Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
📜Introduction
2.
💡Example
3.
📜Naive Approach
4.
📜Optimal Approach
4.1.
🤔Gosper’s Hack
4.1.1.
🧑‍💻Pseudo Code
5.
Code🧑‍💻
5.1.
📚Output
5.2.
⏳Time complexity
6.
Frequently Asked Questions
6.1.
What's wrong with vertex cover, exactly?
6.2.
What vertex cover is the smallest?
6.3.
Does NP have minimum vertex cover?
6.4.
What distinguishes a vertex cover from a dominant set?
6.5.
What makes NP different from NP-hard?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Minimum Vertex Cover Size of a Graph Using Binary Search

Author Mayank Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

📜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.

example

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 TraversalRegular and Bipartite graphsWhat Is Web2Py?Why To Use Web2py?Postbacks and Internationalization in web2pyThird Party Modules In Web2pyTasks In Web2py, and  XML in Web2py.

Happy Coding!

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp
Previous article
Minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B.
Next article
Find the minimum number of edges to be removed such that no path exists between the given pair of vertices
Live masterclass