Vertex Cover — 2-Approximation via Matching

2-approx algorithm

Set vertexCover(List edges) {
  Set cover = new HashSet<>();
  for (int[] e : edges)
    if (!cover.contains(e[0]) && !cover.contains(e[1])) {
      cover.add(e[0]); cover.add(e[1]);
    }
  return cover;
}

Why 2-approx

Maximal matching M has |M| edges, each requires ≥ 1 vertex in cover. OPT ≥ |M|. Our cover: 2|M| = 2·OPT.

Hardness

PCP theorem: no (2-ε)-approx unless P=NP. This is tight.

LP-based

Half-integral LP relaxation. Round variables ≥ 1/2 to 1. Same 2-approx.