Last Updated: 8 Jan, 2021
Vertex Cover Problem
Moderate
Asked in companies
You have been given an undirected graph having ‘N’ nodes. A matrix ‘E’ of size 'M' x 2 is given which represents the ‘M’ edges such that there is an edge directed from node 'E[i][0]' to node 'E[i][1]'. You are supposed to return the size of the set of the minimum number of nodes from which all the other nodes are reachable (set of nodes/ vertices which contains at least one point of every edge in the given graph).
Example :
In the graph given below:
2 ---- 4 ---- 6
| |
| |
| |
3 ---- 5
Here, the minimum vertex cover involves vertices 3 and 4. All the edges of the graphs are incident on either 3 or 4 vertex of the graph.
Note:
1. Nodes are numbered from 1 to 'N'.
2. Your solution will run on multiple test cases. If you are using global variables make sure to clear them.
Input Format:
The first line of input contains an integer 'T' representing the number of the test case.
The first line of each test case argument given is an integer ‘N’ representing the number of nodes in the graph.
The second line of each test case contains a given integer ‘M’ representing the number of edges.
The next ‘M’ lines in each test case contain a matrix ‘E’ of size 'M' x 2 which represents the ‘M’ edges such that there is an edge directed from node 'E[i][0]' to node 'E[i][1]'.
Output Format:
For each test case, print an integer denoting the size of the set of the minimum number of nodes from which all the other nodes are reachable.
Note:
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
2 <= N <= 31
1 <= M <= N * (N - 1) / 2
1 <= E[i][0], E[i][1] <= N
Where ‘E[i][0]’ and 'E[i][1]' denotes the node numbers of the edge.
Time limit: 1 sec
Approaches
First of all, we need to understand what the question is asking us to do? We can think of it as to find the nodes such that all remaining nodes are directly connected to at least one of the nodes of our selected set.
Now think of an algorithm such that, if we select one node then all the nodes which are adjacent to the selected node need not to be considered as part of the minimum set. Our objective is now to find the minimum k such that at least one subset of size ‘k’ amongst ‘N’Ck subsets is a vertex cover. We know that if the minimum size vertex cover is of size k, then there will exist a vertex cover of all sizes more than k. That is, there will be a vertex cover of size k + 1, k + 2, k + 3, k+4 …, ‘N’.
Let’s imagine a boolean array of size ‘N’ and call it ‘checkCover’. So if vertex cover of size x exists then we put a ‘1’ at xth position, otherwise we put ‘0’.
The array checkCover[] will look like:
| 1 | 2 | 3 | . | . | . | k | . | . | . | n |
| 0 | 0 | 0 | . | . | . | 1 | . | . | . | 1 |
Since the array/list is sorted then it is binary searchable, as no index before k will have a ‘1’, and every index after k will have a ‘1’, so k is the answer. So we can apply Binary Search to find the minimum size vertex set that covers all edges (this problem is equivalent to finding last 1 in ‘checkCover’).
Now the problem is how to generate all subsets of a given size. The idea is to use Gosper’s hack. Gosper’s hack is a technique to get the next number with the same number of bits set. So we set the first x bits from right and generate the next number with x bits set until the number is less than 2 * ‘N’. In this way, we can generate all ‘N’Cx numbers with x bits set.