Vertex cover problem

Basic understanding about vertex cover problem

1. Vertex cover problem Ginu saju S1 M tech 10/17/2016 1

2. APPROXIMATION ALGORITHM An algorithm that returns near optimal solutions is called an Approximation algorithm. Eg : i ) Finding a smallest vertex cover of a graph. ii)Travelling sales man problem iii)Minimum spanning tree 10/17/2016 2

3. VERTEX COVER PROBLEM A vertex cover of an undirected graph is a subset of its vertices such that for every edge ( u,v ) of the graph either ‘u’ or ‘v’ is in vertex cover. 10/17/2016 3

4. VERTEX-COVER-APPROX(G ) Input: An undirected graph G Output: A vertex cover C for G C Empty set HG While H has edges eH.remove Edge vH.origin(e) wH.destination(e) C.add(v) C.add(w) for each f incident to v or w H.remove Edge( ) return C 10/17/2016 4

5. example Show the operation of vertex cover-approx for the given undirected graph G 10/17/2016 5 B D C E F A G e1 e2 e3 e8 e6 e4 e5 e7

6. Solution: The given undirected graph G has 7 vertices and 8 edges. STEP 1: initialize c to the empty set as: c empty set STEP 2 : set H which is copy of the edge set E(G)  E(G) ={e1,e2,e3,e4,e5,e6,e7,e8} 10/17/2016 6

7. STEP 3: Apply while loop according to condition as: while H has edges Then do, eH.remove Edge vH.origin (e) wH.destination (e) 10/17/2016 7

8. select edge ( b,c ) ie ,edge e2 10/17/2016 8 b D C E F A G e1 e2 e3 e8 e6 e4 e5 e7 Edge ( b,c )

9. Here H has edges ( b,c ) Here, ( b,c )  H.remove Edge b  H.origin ( b,c ) c  H.destination ( b,c ) 10/17/2016 9 C H.Destination ( b,c ) H.Remove Edge b H.Origin ( b,c )

10. STEP 4 : Apply, C.add (v) C.add (w) ie , add end points of the choosen edge to C Here, C.add (b) C.add (c) 10/17/2016 10

11. STEP 5:  use for loop to remove edge incident to v or w by using: H.remove edge (f) Here, edge ( a,b ), ( c,e ),( c,d ) are incident to b(v) and c(w) which is shown by dashed : 10/17/2016 11 b C D A E F G

12. STEP 6 : return C NOW, C ={ b,c }  Again start from beginning of vertex-cover-Approx(G) for new edge 10/17/2016 12

13. STEP 7: initialize C C  { b,c } STEP 8: choose H from edge set E(G ),here select edge( e,f ) 10/17/2016 13 c a e f d g Edge( e,f ) b

14. STEP 9: Again apply while loop as : eH.remove Edge vH.origin (e) wH.destination (e) Here, ( e,f )  H.remove Edge e  H.origin ( e,f ) f  H.destination ( e,f ) 10/17/2016 14

15. STEP 10: C.add (v) C.add (e) C.add (w) C.add (f) STEP 11: use for loop to remove edge incident to v or w by using: H.remove edge (f) 10/17/2016 15

16. Here edges ( c,e ),( e,d ),( f,d ) are incident to e,f 10/17/2016 16 b a c e d f g

17. STEP 12 : return C C ={ b,c,e,f } STEP 13: initialize C , again C { b,c,e,f } 10/17/2016 17

18. STEP 14: Choose edge ( d,g ) ,as shown below : 10/17/2016 18 c a e f d g Edge( d,g ) b

19. STEP 15: Apply while loop eH.remove Edge vH.origin (e) wH.destination (e) Here, ( d,g )  H.remove Edge d  H.origin ( d,g ) g  H.destination ( d,g ) 10/17/2016 19

20. STEP 16: use for loop to remove edge incident to v or w . Here edges ( c,d ),( d,e ),( d,f ) are incident to d,g . 10/17/2016 20 b a c e d f g

21. STEP 17: return C C={ b,c,d,e,f,g } STEP 18 : The optimal vertex cover for this problem contains only three vertices: { b,d,e } 10/17/2016 21 b c d a g f e

22. A 2-APPROXIMATION FOR VERTEX COVER Every chosen edge e has both ends in C. 2. But e must be covered by an optimal cover,hence one end of e must be in OPT. 3. Thus, there is atmost twice as many vertices in C as in OPT. 4. ie , C is a 2-approx of OPT. 10/17/2016 22

23. Example From the above example given for vertex Approx(G) we can see from step 17 set c contains six vertices: C = { b,c,d,e,f,g } From step 18 it is also show that OPT-vertex cover Approx(G) contains only vertices: ie ,{ b,d,e } 10/17/2016 23