Set cover problem

The set cover problem is a classical question in combinatorics, computer science and complexity theory. It is one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.

It is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms.

Given a set of elements ${\displaystyle \{1,2,...,n\}}$ (called the universe) and a collection ${\displaystyle S}$ of ${\displaystyle m}$ sets whose union equals the universe, the set cover problem is to identify the smallest sub-collection of ${\displaystyle S}$ whose union equals the universe. For example, consider the universe ${\displaystyle U=\{1,2,3,4,5\}}$ and the collection of sets ${\displaystyle S=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$. Clearly the union of ${\displaystyle S}$ is ${\displaystyle U}$. However, we can cover all of the elements with the following, smaller number of sets: ${\displaystyle \{\{1,2,3\},\{4,5\}\}}$.

...
Wikipedia