SET-COVER is NP-complete

SET-COVER: given a universe U and a family {S₁, …, S_m} of subsets, is there a sub-family of size ≤ k that covers U?

• SET-COVER generalises VERTEX-COVER; the reverse isn't true. Vertex-cover sets correspond to edges incident to a single vertex — a very restricted structure. SET-COVER allows arbitrary sets.
• The reduction is "natural": U = E, S_v = edges-of-v. A vertex cover of size k becomes a set cover of size k. The same k is preserved.
• Greedy gives O(log n) approximation. No constant-factor approximation is possible (assuming P ≠ NP). SET-COVER is the canonical hard-to-approximate problem.

• Q1. Why is the correspondence one-to-one?
  Each vertex of G maps to a set in the system; each edge maps to an element of the universe. Covering all edges in G = covering all elements of U. The size k is preserved exactly.
• Q2. Why is SET-COVER even more general?
  Not every set system comes from a graph (sets can overlap arbitrarily, not just by sharing a vertex). SET-COVER captures arbitrary covering problems; VERTEX-COVER is the special case where sets correspond to vertex-incidence relations.
• Q3. Greedy approximation?
  Picking the set that covers the most uncovered elements gives an O(log n) approximation to SET-COVER. This is tight — no better approximation exists (Feige 1998, under P ≠ NP).
• Q4. What about WEIGHTED SET-COVER?
  Each set has a cost; minimise total cost. Still NP-hard, still O(log n)-approximable by weighted greedy. Many real-world facility-location problems are weighted set-cover.

Sipser: §7.5 (NP-completeness extensions). Lecture notes: Module 5 slide 5. Companion problems: P28 (CLIQUE → VC).