Note: I've already looked at the solution from "Textbook Solutions" but could really use another perspective on it. I've included the algorithm and an example of it in action below.

Example of the algorithm being used:

35.1-2 Prove that the set of edges picked in line 4 of APPRox-VERTEX-COVER forms a maximal matching in the graph G APPROX-VERTEX-COVER (G) 2 EG.E while E 4 let (u, v) be an arbitrary edge of E 6 7 return C remove from E' every edge incident on either u or Figure 35.1 illustrates how APPROX-VERTEX-COVER operates on an example graph. The variable C contains the vertex cover being constructed. Line1 ini- tializes C to the empty set. Line 2 sets E' to be a copy of the edge set G.E of the graph. The loop of lines 3-6 repeatedly picks an edge (u, v) from E, adds its Chapter 35 Approximation Algorithms endpoints u and v to C, and deletes all edges in E' that are covered by either u or v. Finally, line 7 returns the vertex cover C. The running time of this algorithm is O(V E), using adjacency lists to represent E (l Figure 35.1 The operation of APPROX VERTEX COVER. (a) The input graph G, which has 7 vertices and 8 edges. (b) The edge (b, c), shown heavy, is the first edge chosen by APPROX VERTEX COVER. Vertices b and c, shown lightly shaded, are added to the set C containing the vertex cover being created. Edges (a, b), (c, e), and (c,d), shown dashed, are removed since they are now covered by some vertex in C. (c) Edge (e,f) is chosen; vertices e and f are added to C. (d) Edge (d.g) is chosen; vertices d and g are added to C. (e) The set C, which is the vertex cover produced by APPROX VERTEX COVER,contains the six vertices b, c, d, e, f g. (f The optimal vertex cover for this problem contains only three vertices: b, d, and e