A vertex-cover of an undirected graph G = (V, E) is a subset of vertices V '  ⊆ V such that if edge (u, v) is an edge of G, then either u in V or v in V '  or both.

Find a vertex-cover of maximum size in a given undirected graph. This optimal vertexcover is the optimization version of an NP-complete problem. However, it is not too hard to find a vertex-cover that is near optimal.

APPROX-VERTEX_COVER (G: Graph) c ← { } E ' ← E[G]

while E ' is not empty do

Let (u, v) be an arbitrary edge of E ' c ← c U {u, v}

Remove from E ' every edge incident on either u or v

return c