Vertex cover problem in a given graph is a problem to find the minimum number of vertices which covers every edges in graph. The minimum number of vertices is a subset of vertices. Here covering of every edge means, at least one of end point of every edge falls into the subset. we can also say that at least end point of every edge is member of subset.

In mathematical term above concept can be summarized as, Given a graph G=(V,E) where V denotes vertex and E denotes edge, find a smallest subset V’ ⊆ V such that if ( u,v) ∈ E then u ∈ V’ or v ∈ V’ or both. Let us take an example graph. Vertex cover problem is NP complete problem.

vertex cover problem in graphWe can easily observe that in above graph we found a possible subset V’= {2,3,5} ( set of vertex) , where every edge (1,2), (2,1),(1,3),(3,1), (2,3),(3,2),(3,4),(4,3),(4,5),(5,4),(2,5) and (5,2) is covered by subset V’= {2,3,5} i.e at least one of end point of these edges is in subset V’={2,3,5}. Note: The subset V’ is one of the solution of vertex cover problem, the subset may contain different vertices in it but the size of vertex cover (subset) will be always same.

How to solve vertex cover problem, greedy approach

  1. Create an empty set S.
  2. select an edge E(u,v) from graph.
  3. If any edge’s end point u or v is in set S, then the edge E(u,v) is already covered. else
  4. Insert vertex u and vertex v in set S. mark this edge E(u,v)  covered.
  5. go to step 2, select next uncovered edge.
  6. The algorithm terminates , when all edges are processed, i.e there is no uncovered edge available.

Here is sample implementation of above greedy approach. An array of size equal to the number of vertices,can be used as the set S. for example if there are 5 nodes, create an array S of size 5.

S[5] = {-1,-1,-1,-1,-1}

Let an Edge( 0,2) is taken to find vertex cover

now 0 and 2 are not member of S.

Then insert these vertices in set S. like below

S[0] = 1, S[2]=1, here index of 0 and 1 will be true. S[5] ={1,-1,1,-1,-1}

Let next edge to be process to find cover vertex is E(2,1)

Then to be part of vertex cover ,vertex 2 and vertex 1 should not be member of set S.

we can check membership of 2 easily. if  (S[2] == 1 ) evaluates to true.

Related Contents to follow