Problem

  • Input: undirected graph G = (V, E) with |V| = n, |E| = m (15:16).
  • Goal: pick a smallest subset S of vertices so every edge is incident on at least one vertex of S (16:20).

Vertex cover is a special case of set cover

  • Universe = the edges; sets = the vertices (each vertex is the set of edges incident on it) (17:09, 17:52).
  • A student catches a subtlety: the H_K set-cover bound is keyed to set size, and vertices can have high degree, so it does not immediately give 2 here (19:35).
  • The right dual statement: if every element lies in at most K sets, you get a K-approximation — and every edge lies in exactly 2 vertex-sets (20:02).

The greedy (combinatorial) algorithm

while there exists an uncovered edge e = (u, v):
    add both u and v to the cover

(17:52)

Claim: greedy is a 2-approximation (18:33).

Classic matching proof (sketched): the edges picked across the loop's iterations form a matching; the returned set has exactly twice that matching's size; and any vertex cover is lower-bounded by the size of any matching (18:33, 19:14).

LP formulation

Primal (20:40, 21:15):

  • minimize sum_{v=1..n} x_v
  • subject to x_u + x_v >= 1 for every edge e = (u,v), and x >= 0
  • This is essentially the set cover LP (21:43).

Dual (21:43):

  • maximize sum_{e in E} y_e
  • subject to sum_{e containing v} y_e <= 1 for every vertex v, and y >= 0

Alternative: LP rounding

  1. Solve the primal LP, getting fractional x (22:32).
  2. For each edge constraint x_u + x_v >= 1, at least one of x_u, x_v is >= 1/2; take that vertex (22:49, 23:10).
  3. Rounding at most doubles each value, so the cost at most doubles: another 2-approximation (23:10, 23:30).

Generalization: the same threshold rounding gives a K-approximation for set cover when each element is in at most K sets — the constraint has K variables summing to >= 1, so one of them is >= 1/K (23:30, 23:45).

Trade-off: greedy is fast because it never solves an LP; LP rounding is slower. This is why the combinatorial algorithm deserves its own primal-dual analysis (22:32, 23:59).

Primal-dual analysis of greedy

When greedy covers edge e = (u,v) (24:28):

  • set x_u = 1 and x_v = 1;
  • set y_e = 1.

Key points:

  • This is pure primal-dual, not dual fitting — dual feasibility comes out automatically, with no rescaling (24:28).
  • Both solutions are feasible; each unit of dual increase raises the primal by at most 2 (only 1 if a vertex was already taken) (25:09).
  • Therefore primal cost <= 2 * dual cost <= 2 * OPT — a 2-approximation (25:44).
flowchart LR
    A["Uncovered edge e = (u,v)"] --> B["Primal: x_u = 1, x_v = 1<br/>(cost +2 at most)"]
    A --> C["Dual: y_e = 1<br/>(cost +1)"]
    B --> D["Primal feasible<br/>(loop ends only when all edges covered)"]
    C --> E["Dual feasible automatically<br/>(picked edges form a matching)"]
    D --> F["primal <= 2 x dual <= 2 x OPT"]
    E --> F

Homework preview: weighted vertex cover

  • On the problem set the vertices carry weights: minimize sum_v c_v * x_v (25:44).
  • Open question posed to students: should you still take both endpoints? Probably not when one is far cheaper — reasoning about primal and dual together suggests the right modification (26:15).