Finding minimum vertex cover size of a graph using binary search | A Java 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
class GFG { static final int maxn = 25 ; static boolean [ ] [ ] gr = new boolean [ maxn ] [ maxn ] ; static boolean isCover ( int V , int k , int E ) { int set = ( 1 << k ) - 1 ; int limit = ( 1 << V ) ; boolean [ ] [ ] vis = new boolean [ maxn ] [ maxn ] ; ; while ( set < limit ) { for ( int i = 0 ; i < maxn ; i ++ ) { for ( int j = 0 ; j < maxn ; j ++ ) { vis [ i ] [ j ] = false ; } } int cnt = 0 ; for ( int j = 1 , v = 1 ; j < limit ; j = j << 1 , v ++ ) { if ( ( set & j ) != 0 ) { for ( int co = 1 ; co <= V ; co ++ ) { if ( gr [ v ] [ co ] && ! vis [ v ] [ co ] ) { vis [ v ] [ co ] = true ; vis [ co ] [ v ] = true ; cnt ++ ; } } } } if ( cnt == E ) return true ; int co = set & - set ; int ro = set + co ; set = ( ( ( ro ^ set ) >> 2 ) / co ) | ro ; } return false ; } static 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 ; } static void insertEdge ( int u , int v ) { gr [ u ] [ v ] = true ; gr [ v ] [ u ] = true ; } public static void main ( String [ ] args ) { int V = 6 , E = 6 ; insertEdge ( 1 , 2 ) ; insertEdge ( 2 , 3 ) ; insertEdge ( 1 , 3 ) ; insertEdge ( 1 , 4 ) ; insertEdge ( 1 , 5 ) ; insertEdge ( 1 , 6 ) ; System . out . print ( " Minimum ▁ size ▁ of ▁ a ▁ vertex ▁ cover ▁ = ▁ " + findMinCover ( V , E ) + "NEW_LINE"); for ( int i = 0 ; i < maxn ; i ++ ) { for ( int j = 0 ; j < maxn ; j ++ ) { gr [ i ] [ j ] = false ; } } 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 ) ; System . out . print ( " Minimum ▁ size ▁ of ▁ a ▁ vertex ▁ cover ▁ = ▁ " + findMinCover ( V , E ) + "NEW_LINE"); } }