Finding minimum vertex cover size of a graph using binary search | A Python3 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 ; 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
maxn = 25 NEW_LINE gr = [ [ None ] * maxn for i in range ( maxn ) ] NEW_LINE def isCover ( V , k , E ) : NEW_LINE INDENT Set = ( 1 << k ) - 1 NEW_LINE limit = ( 1 << V ) NEW_LINE vis = [ [ None ] * maxn for i in range ( maxn ) ] NEW_LINE while ( Set < limit ) : NEW_LINE INDENT vis = [ [ 0 ] * maxn for i in range ( maxn ) ] NEW_LINE cnt = 0 NEW_LINE j = 1 NEW_LINE v = 1 NEW_LINE while ( j < limit ) : NEW_LINE INDENT if ( Set & j ) : NEW_LINE INDENT for k in range ( 1 , V + 1 ) : NEW_LINE INDENT if ( gr [ v ] [ k ] and not vis [ v ] [ k ] ) : NEW_LINE INDENT vis [ v ] [ k ] = 1 NEW_LINE vis [ k ] [ v ] = 1 NEW_LINE cnt += 1 NEW_LINE DEDENT DEDENT DEDENT j = j << 1 NEW_LINE v += 1 NEW_LINE DEDENT if ( cnt == E ) : NEW_LINE INDENT return True NEW_LINE DEDENT c = Set & - Set NEW_LINE r = Set + c NEW_LINE Set = ( ( ( r ^ Set ) >> 2 ) // c ) | r NEW_LINE DEDENT return False NEW_LINE DEDENT def findMinCover ( n , m ) : NEW_LINE INDENT left = 1 NEW_LINE right = n NEW_LINE while ( right > left ) : NEW_LINE INDENT mid = ( left + right ) >> 1 NEW_LINE if ( isCover ( n , mid , m ) == False ) : NEW_LINE INDENT left = mid + 1 NEW_LINE DEDENT else : NEW_LINE INDENT right = mid NEW_LINE DEDENT DEDENT return left NEW_LINE DEDENT def insertEdge ( u , v ) : NEW_LINE INDENT gr [ u ] [ v ] = 1 NEW_LINE gr [ v ] [ u ] = 1 NEW_LINE DEDENT V = 6 NEW_LINE E = 6 NEW_LINE insertEdge ( 1 , 2 ) NEW_LINE insertEdge ( 2 , 3 ) NEW_LINE insertEdge ( 1 , 3 ) NEW_LINE insertEdge ( 1 , 4 ) NEW_LINE insertEdge ( 1 , 5 ) NEW_LINE insertEdge ( 1 , 6 ) NEW_LINE print ( " Minimum ▁ size ▁ of ▁ a ▁ vertex ▁ cover ▁ = ▁ " , findMinCover ( V , E ) ) NEW_LINE gr = [ [ 0 ] * maxn for i in range ( maxn ) ] NEW_LINE V = 6 NEW_LINE E = 7 NEW_LINE insertEdge ( 1 , 2 ) NEW_LINE insertEdge ( 1 , 3 ) NEW_LINE insertEdge ( 2 , 3 ) NEW_LINE insertEdge ( 2 , 4 ) NEW_LINE insertEdge ( 3 , 5 ) NEW_LINE insertEdge ( 4 , 5 ) NEW_LINE insertEdge ( 4 , 6 ) NEW_LINE print ( " Minimum ▁ size ▁ of ▁ a ▁ vertex ▁ cover ▁ = ▁ " , findMinCover ( V , E ) ) NEW_LINE