Finding minimum vertex cover size of a graph using binary search | A C ++ program to find size of minimum vertex cover using Binary Search ; Global array to store the graph Note : since the array is global , all the elements are 0 initially ; Returns true if there is a possible subset of size ' k ' that can be a vertex cover ; Set has first ' k ' bits high initially ; to mark the edges covered in each subset of size ' k ' ; Reset visited array for every subset of vertices ; set counter for number of edges covered from this subset of vertices to zero ; selected vertex cover is the indices where ' set ' has its bit high ; Mark all edges emerging out of this vertex visited ; If the current subset covers all the edges ; Generate previous combination with k bits high set & - set = ( 1 << last bit high in set ) ; Returns answer to graph stored in gr [ ] [ ] ; Binary search the answer ; at the end of while loop both left and right will be equal , / as when they are not , the while loop won 't exit the minimum  size vertex cover = left = right ; Inserts an edge in the graph ; Undirected graph ; Driver code ; 6 / 1 -- -- - 5 vertex cover = { 1 , 2 } / | \ 3 | \  \ | \ 2 4 ; Let us create another graph ; 2 -- -- 4 -- -- 6 / | | 1 | | vertex cover = { 2 , 3 , 4 } \ | | 3 -- -- 5
#include <bits/stdc++.h> NEW_LINE #define maxn  25 NEW_LINE using namespace std ; bool gr [ maxn ] [ maxn ] ; bool isCover ( int V , int k , int E ) { int set = ( 1 << k ) - 1 ; int limit = ( 1 << V ) ; bool vis [ maxn ] [ maxn ] ; while ( set < limit ) { memset ( vis , 0 , sizeof vis ) ; int cnt = 0 ; for ( int j = 1 , v = 1 ; j < limit ; j = j << 1 , v ++ ) { if ( set & j ) { for ( int k = 1 ; k <= V ; k ++ ) { if ( gr [ v ] [ k ] && ! vis [ v ] [ k ] ) { vis [ v ] [ k ] = 1 ; vis [ k ] [ v ] = 1 ; cnt ++ ; } } } } if ( cnt == E ) return true ; int c = set & - set ; int r = set + c ; set = ( ( ( r ^ set ) >> 2 ) / c ) | r ; } return false ; } int findMinCover ( int n , int m ) { int left = 1 , right = n ; while ( right > left ) { int mid = ( left + right ) >> 1 ; if ( isCover ( 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 ; } int main ( ) { int V = 6 , E = 6 ; insertEdge ( 1 , 2 ) ; insertEdge ( 2 , 3 ) ; insertEdge ( 1 , 3 ) ; insertEdge ( 1 , 4 ) ; insertEdge ( 1 , 5 ) ; insertEdge ( 1 , 6 ) ; cout << " Minimum ▁ size ▁ of ▁ a ▁ vertex ▁ cover ▁ = ▁ " << findMinCover ( V , E ) << endl ; memset ( gr , 0 , sizeof gr ) ; 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 ▁ = ▁ " << findMinCover ( V , E ) << endl ; return 0 ; }