the set covering problem (scp) is a classical question in combinatorics, computer science and complexity theory. it is a problem "whose study has led to the development of fundamental techniques for the entire field" of approximation algorithms. it was also one of karp's 21 np-complete problems shown to be np-complete in 1972. given a set of elements \{1,2,...,m\} (called the universe) and a set s of n sets whose union equals the universe, the set cover problem is to identify the smallest subset of s whose union equals the universe. for example, consider the universe u = \{1, 2, 3, 4, 5\} and the set of sets s = \{\{1, 2, 3\}, \{2, 4\}, \{3, 4\}, \{4, 5\}\}. clearly the union of s is u. however, we can cover all of the elements with the following, smaller number of sets: \{\{1, 2, 3\}, \{4, 5\}\}. more formally, given a universe \mathcal{u} and a family \mathcal{s} of subsets of \mathcal{u}, a cover is a subfamily \mathcal{c}\subseteq\mathcal{s} of sets whose union is \mathcal{u}. in the set covering decision problem, the input is a pair (\mathcal{u},\mathcal{s}) and an integer k; the question is whether there is a set covering of size k or less. in the set covering optimization problem, the input is a pair (\mathcal{u},\mathcal{s}), and the task is to find a set covering that uses the fewest sets. the complexity of set cover problem is m^n where m is the size of the universe and n is the number of sets in the collection s. the decision version of set covering is np-complete, and the optimization version of set cover is np-hard . if each set is assigned a cost, it becomes a weighted set cover problem.  ==integer linear program formulation== the minimum set cover problem can be formulated as the following integer linear program (ilp). {| | minimize | \sum_{s \in \mathcal s} x_s | | (minimize the number of sets) |- | subject to | \sum_{s\colon e \in s} x_s \geqslant 1 | for all e\in \mathcal u | (cover every element of the universe) |- | | x_s \in \{0,1\} | for all s\in \mathcal s. | (every set is either in the set cover or not) |} this ilp belongs to the more general class of ilps for covering problems. the integrality gap of this ilp is at most \scriptstyle \log n, so its relaxation gives a factor-\scriptstyle \log n approximation algorithm for the minimum set cover problem (where \scriptstyle n is the size of the universe). == hitting set formulation == set covering is equivalent to the hitting set problem. it is easy to see this by observing that an instance of set covering can be viewed as an arbitrary bipartite graph, with sets represented by vertices on the l
NP-complete_problems Set_families