(VC) MINIMUM VERTEX COVER Instance: Graph G=(V,E), for each vertex v in V a weight W(v)>=0; Solution: A vertex cover for G, i.e., a subset C of V such that, for each edge (v,u) in E, at least one of u and v are in C; Measure : W(C) (i.e. Sum {W(v): v in C}) +----------------------------------------------------------------+ | The "Local-Ratio Theorem" (oriented for VC) | +----------------------------------------------------------------+ | If C is 2-approximation VC w.r.t the weight function W1 | | and C is 2-approximation VC w.r.t the weight function W2 | | then C is 2-approximation VC w.r.t the weight function W1+W2 | +----------------------------------------------------------------+ Let (v,u) be any edge s.t. epsilon>0 where: epsilon = Min(W(v),W(u)) define W1(v) = W1(u) = epsilon and 0 for all others. Q1: All vertex covers are 2-approximations w.r.t W1. Why? The algorithm: iteratively subtract W1 as above. Induction hyp. implies that reclusive call with W2=W-W1 would return a vertex cover C which is 2-approximation w.r.t. W2. C (and any vertex cover) is 2-approximation w.r.t. W1 (see Q1). By the "Local-Ratio Theorem" C is 2-approximation w.r.t. W=W1+W2. Q2: What to do with zero weight vertices? Hence: The following linear time algorithm is 2-approximation. +-------------------------------------+ | Algorithm Bar-Yehuda&Even(G,W) | +-------------------------------------+ | for each edge (v,u) | | Let epsilon = Min(W(v),W(u)) | | W(v) -= epsilon | | W(u) -= epsilon | | return {v: W(v)=0} | +-------------------------------------+