Greedy Approximations: Vertex Cover and Set Cover

Two cover problems, both hard

From the previous guide you carry one definition everywhere now: an algorithm is an alpha-approximation if, on every input, it returns a feasible solution whose cost is within a factor of alpha of the optimum — a worst-case approximation ratio, not a typical-case promise. This guide spends that idea on the two most famous covering problems, and the two greedy algorithms that tame them. Both problems are NP-hard, so we are not hoping for the exact optimum; we are hunting for a fast algorithm with a guarantee we can prove.

First, vertex cover. Given an undirected graph, a vertex cover is a set of vertices that touches every edge — for each edge, at least one of its two endpoints is in the set. We want the smallest such set. You met its decision version when complexity was being built, and the hardness reduction into vertex cover is what stamps it NP-hard. Picture a museum floor plan where corridors are edges and you must station a guard at a room (vertex) so every corridor is watched by at least one end: vertex cover is "fewest guards."

Second, set cover, the more general beast. You are given a universe of n elements and a family of subsets that together cover everything; you want to pick the fewest subsets whose union is still the whole universe. Vertex cover is actually a special case — let each vertex be a set containing the edges it touches, and "cover all edges" becomes "cover the universe of edges." So set cover is at least as hard, and as we will see, its best greedy guarantee is genuinely weaker. Two problems, two greedy ideas; the lesson is which greedy you choose and why its proof closes.

Vertex cover: the greedy that fails, and the one that works

The instinctive greedy is to repeatedly grab the highest-degree vertex — the one covering the most uncovered edges — delete its edges, and repeat. It feels unbeatable, but "looks locally best" is never a proof, and here it is not even within a constant factor: there are graphs where this max-degree greedy returns about (log n) times the optimum. This is the same trap as 0/1 knapsack — a plausible local rule with no guarantee. So we abandon it, not because it never works, but because it has no provable factor.

Here is the algorithm that does work, and its idea is delightfully sideways. Instead of choosing vertices, choose an edge. Pick any uncovered edge (u, v), add both endpoints u and v to your cover, delete every edge now covered by u or v, and repeat until no edges remain. Adding both endpoints looks wasteful — surely one would do? — but that apparent waste is exactly what makes the proof go through. The edges you pick, one per round, form a matching: no two of them share an endpoint, because once an edge is chosen, both its endpoints are removed along with all their edges.

VertexCoverApprox(G):
  C = {}                         # the cover we build
  M = {}                         # the matching we pick, one edge per round
  while G still has an edge:
    pick any edge (u, v)
    C = C union {u, v}           # add BOTH endpoints
    M = M union {(u, v)}
    delete u, v and all their incident edges from G
  return C                       # |C| = 2 * |M|

First, is the output even a valid cover? Yes: the loop only stops when no edge is left, and an edge can vanish only by having an endpoint added to C, so every original edge ends up touched. The algorithm is also fast — one pass over the edges, O(n + m) time, the kind of cheap loop you have written since the foundations. Feasibility and speed are the easy half; the guarantee is where the cleverness hides.

Why it is a 2-approximation

The whole proof rests on a lower bound on the optimum, which is the recurring move in this entire rung: to bound how far above OPT you are, you first need something you know is at most OPT. Here that something is the matching M. Consider its edges; they share no endpoints. Any vertex cover — including the optimal one — must include at least one endpoint of every edge, so it must spend at least one distinct vertex on each edge of M. No single vertex can cover two matching edges, since they are disjoint. Therefore OPT, the size of the smallest cover, is at least |M|.

1. The cover we return is C, with exactly |C| = 2*|M| vertices — two endpoints per matching edge, and the matching edges are disjoint so no vertex is double-counted.
2. Any vertex cover must use at least one vertex per matching edge, and those vertices are all different, so OPT is at least |M|. This is the load-bearing lower bound.
3. Chain them: |C| = 2*|M| <= 2*OPT. So C never exceeds twice the optimum — a factor-2 guarantee on every single input.

Read what just happened, because the shape recurs throughout approximation. We never computed OPT — it is NP-hard, we cannot. We compared our answer to a quantity (|M|) sandwiched between us and OPT: |M| <= OPT <= |C| = 2*|M|. The matching is a certificate of near-optimality we build for free while running the algorithm. That is the art of these proofs: find a lower bound on OPT that the algorithm itself hands you, then show your output stays within alpha of it.

Set cover: greedy by coverage

For set cover the matching trick has nothing to bite on, so we go back to an honest greedy — and this time it earns its keep. The greedy set cover rule: at each step pick the set that covers the most still-uncovered elements, add it to the solution, mark those elements covered, and repeat until everything is covered. It is the natural "most bang per pick" heuristic, an instance of the greedy choice at work. Unlike the max-degree rule for vertex cover, here the greedy choice does come with a provable bound — but a weaker, logarithmic one, and watching the gap appear is the point of this section.

The analysis uses a charging argument so clean it is worth carrying with you. When greedy picks a set covering k brand-new elements, we charge that one chosen set to those k elements, giving each newly covered element a cost of 1/k. The total cost spread this way equals the number of sets greedy picks — every chosen set hands out exactly 1 unit of cost — so adding up all the per-element charges gives precisely the size of greedy's solution. The trick is then to bound the charge an individual element receives.

Fix any one optimal set S in the hidden optimum, and number its elements by the order greedy covers them — last-covered first: e_1, e_2, ..., down to the final one. When greedy was about to cover e_i, all i of the elements e_1..e_i in S were still uncovered, so S itself was an available choice covering at least i of them. Greedy always grabs the most-covering set, so it covered at least i new elements that round, meaning e_i was charged at most 1/i. Sum over the elements of S: its total charge is at most 1/1 + 1/2 + ... up to its size, which is the harmonic number H_|S|, at most H_n where n is the universe size, and H_n is about (ln n).

Now finish. The optimum uses OPT sets, and every element of the universe lives in at least one of them. The whole charge greedy pays is at most the charges summed over the OPT optimal sets, each at most H_n, so greedy's size is at most H_n * OPT — about (ln n)*OPT. That is the headline: greedy set cover is an H_n-approximation, a roughly (ln n)-factor guarantee. Slower-growing than any constant, but still polynomially close, and from one beautifully simple rule.

Why constant for one, logarithmic for the other

It is fair to feel uneasy: vertex cover is a special case of set cover, yet vertex cover gets a tidy factor 2 while general set cover only gets (ln n). No contradiction — a special case can simply have more structure to exploit. Vertex cover's gift is that every "set" (a vertex's edges) is matched against a partner of size two: every edge has exactly two endpoints, so the disjoint-matching lower bound exists. General set cover has no such bound on how its sets overlap, so the weaker harmonic argument is the best the greedy can promise.

Step back and collect the toolkit. A greedy approximation needs three things checked, in order: feasibility (the output is a valid solution), running time (it is polynomial), and the ratio (a lower bound on OPT that the run itself supplies, against which your output is bounded). The vertex-cover proof handed us that bound as a matching; the set-cover proof manufactured it by charging cost to elements. The next guides keep the recipe and change the lower bound: metric TSP leans on the MST and a shortcutting tour, and after that we will let a linear program supply the lower bound, then round its fractional answer back to a whole one.