Approx Vertex Cover

Is an Approximation Algorithm for solving the Vertex Cover Problem.

Pseudocode

Takes as input an Undirected Graph $G$ and returns a vertex cover no more than twice the size of the optimal vertex cover.

def approx_vertex_cover(G: Graph) -> Set[int]:
    # Initialize empty vertex cover
    C: Set[int] = set()
    # Make a copy of edges to work with
    E_prime = edges.copy()
 
    # While there are edges remaining
    while len(E_prime > 0):
        # Get an arbitrary edge from E'
        u, v = next(iter(E_prime))
 
        C.add(u)
        C.add(v)
        remove_incident_edges(u, v, E_prime)
    return C
 
def remove_incident_edges(u, v, E):
    for edge in E:
        x, y = edge
        if u in (x, y) or v in (x, y):
            E -= edge
    return E

Runs in $O(V+E)$ time.

Optimality

We have that approx_vertex_cover is a polynomial-time 2-approximation algorithm.

Proof

CLRS p. 1110.

Examples

(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$.