Set cover problem

Set covering (also known as set cover) is a classical computer science problem.

As input you are given several sets. They may have some elements in common. You must select some of these sets so that the sets you have picked contain all the elements that are contained in any of the sets in the input.

More formally, the input if a set of sets. We'll denote each of these sets with $S_{i}$, so the first set is $S_{0}$, the second $S_{1}$, and so on. We'll use the letter $n$ to indicate the number of input sets, so the last input set is $S_{n-1}$.

A solution to the set covering problem is a selection of the input sets, which we can indicate by giving the number of each set that we chose. That is, a solution is a set $C$ of elements in $[0..(n-1)]$. The solution $C$ has two properties. First, it includes all elements of the input sets, so $\bigcup _{j\in C}S_{j}=\bigcup _{i<n}S_{i}$. Second, there is no way to pick fewer of the input sets and still cover all the elements: $\not \exists D:|D|<|C|{\mbox{ and }}\bigcup _{j\in D}S_{j}=\bigcup _{i<n}S_{i}$

The most direct way of solving set cover is to try all combinations of sets (known as "brute force"). This can naturally be improved upon (for example by trying the larger sets first, an approach known as "greedy set cover"). It has been shown that the set cover problem is NP-hard, so no deterministic algorithm can be faster than brute force for every possible input of the problem.