Set cover problem
|
|
The set cover problem (also set covering) is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number 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. It was one of Karp's 21 NP-complete problems shown to be NP-complete in 1972.
More formally, the input is a set of sets denoted <math>S_i<math>, so the first set is <math>S_0<math>, the second <math>S_1<math>, and so on. Use n to indicate the number of input sets, so the last input set is <math>S_{n-1}<math>.
A solution to the set covering problem is a selection of a minimum number of the input sets, which we can indicate by giving the index numbers of each set that we chose. That is, a solution is a subset <math>C<math> of {0, 1, ..., n − 1}. The solution <math>C<math> has two properties. First, it includes all elements of the input sets, so
- <math> \bigcup_{j\in C} S_j = \bigcup_{i
Second, there is no way to pick fewer of the input sets and still cover all the elements:
- <math>\not\exists D : |D|<|C| \mbox{ and } \bigcup_{j\in D} S_j = \bigcup_{i
The most direct way (known as "brute force") of solving set cover is to try all combinations of sets. This can 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.
Related problems are vertex cover, set packing, and edge cover.
The set cover problem can be seen as a finite version of the notion of compactness in topology, where the elements of certain infinite families of sets can be covered by choosing only finitely many of them.