The vertex-cover problem

The vertex-cover problem

A vertex cover of an undirected graph G (V,E) is a subset V ‘ Vsuch that if (u,v)  is an edge of G, then either u  V’ or v  V’(or both). The size of a vertex cover is the number of vertices in it.

The vertex-cover problem is to find a vertex cover of minimum size in a given undirected graph. Such a vertex cover is called as an optimal vertex cover. This problem is the optimization version of an NP-complete decision problem.

The following approximation algorithm takes as input an undirected graph G and returns a vertex cover whose size is guaranteed to be no more than twice the size of an optimal vertex cover.

Example: Given a graph G with 7 vertices and 8 edges

Steps explained:

a. given graph G.

b. consider edge(b,c) then the edges going out from b and c are removed(dashed line)

c. consider edge(e,f) then the outgoing edges removed

d. consider edge(d,g)

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. optimal vertex cover for this problem contains only three vertices: b, d, and e.