Set cover problem

The set cover problem is a classical question in combinatorics, computer science, operations research and complexity theory. Given a universe of elements and a collection of subsets whose union equals that universe, the task is to identify a smallest sub-collection of the subsets whose union still equals the universe. In its decision form the input is the universe, the collection and an integer k, and the question is whether a cover of size k or less exists; in its optimization form the task is to find a cover that uses the fewest sets. The decision version is NP-complete and is one of Karp's 21 NP-complete problems, shown to be NP-complete in 1972, while the optimization or search version is NP-hard. Its study led to fundamental techniques in the field of approximation algorithms.