Approximation algorithm for Vertex Cover Consider the following algorithm that t

Question

Approximation algorithm for Vertex Cover Consider the following algorithm that takes as input undirected graph G = (V, E) and returns a set of nodes S: 1. Initialize set S = 0 2. While E notequalto 0 do (a) Pick any edge (u, v) elementof E, add u, v to S (b) Remove all edges incident to u and all edges incident to v from E 3. Return S Prove that this EasyVC returns vertex cover of G What is the runtime of EasyVC? Assume that G is given by its adjacency matrix. Is the set S always an optimal vertex cover? if not, give an example when it is not optimal. How 'bad' is it in your example? i.e. how much smaller is optimal vertex cover VC(G)? What is the approximation ratio in your example? Try to find example when it is as big as it gets. Prove the approximation ratio for EasyVC

Explanation / Answer

Claim 1: This algorithm gives a vertex cover
Proof: Every edge 2 M is clearly covered. If an edge, e /2 M is not covered, then M [ {e} is a
matching, which contradict to maximality of M.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.