Skip to main content

Set cover is a well-known NP-complete problem: given a collection of sets, find as small as possible a subcollection whose union is the same as the union of the entire collection.

Set cover is one of the original NP-complete problems in Karp's foundational paper. Given a collection of sets F with union U, the goal is to find a subset G⊆F, as small as possible, which also covers U. The greedy algorithm gives a logn approximation, which is worst-case optimal unless P=NP.