# Set cover problem

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.

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 .Template:Sfn

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).

This ILP belongs to the more general class of ILPs for covering problems. The integrality gap of this ILP is at most $\log n$ , so its relaxation gives a factor-$\log n$ approximation algorithm for the minimum set cover problem (where $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 left, the universe represented by vertices on the right, and edges representing the inclusion of elements in sets. The task is then to find a minimum cardinality subset of left-vertices which covers all of the right-vertices. In the Hitting set problem, the objective is to cover the left-vertices using a minimum subset of the right vertices. Converting from one problem to the other is therefore achieved by interchanging the two sets of vertices.

## Greedy algorithm

The greedy algorithm for set covering chooses sets according to one rule: at each stage, choose the set that contains the largest number of uncovered elements. It can be shown that this algorithm achieves an approximation ratio of $H(s)$ , where $s$ is the size of the set to be covered, $H(n)$ is the $n$ -th harmonic number:

$H(n)=\sum _{k=1}^{n}{\frac {1}{k}}\leq \ln {n}+1$ There is a standard example on which the greedy algorithm achieves an approximation ratio of $\log _{2}(n)/2$ . The universe consists of $n=2^{(k+1)}-2$ elements. The set system consists of $k$ pairwise disjoint sets $S_{1},\ldots ,S_{k}$ with sizes $2,4,8,\ldots ,2^{k}$ respectively, as well as two additional disjoint sets $T_{0},T_{1}$ , each of which contains half of the elements from each $S_{i}$ . On this input, the greedy algorithm takes the sets $S_{k},\ldots ,S_{1}$ , in that order, while the optimal solution consists only of $T_{0}$ and $T_{1}$ . An example of such an input for $k=3$ is pictured on the right.

Inapproximability results show that the greedy algorithm is essentially the best-possible polynomial time approximation algorithm for set cover (see Inapproximability results below), under plausible complexity assumptions.

## Low-frequency systems

If each element occurs in at most f sets, then a solution can be found in polynomial time that approximates the optimum to within a factor of f using LP relaxation.

## Inapproximability results

When $n$ refers to the size of the universe, Template:Harvtxt showed that set covering cannot be approximated in polynomial time to within a factor of ${\tfrac {1}{2}}\log _{2}{n}\approx 0.72\ln {n}$ , unless NP has quasi-polynomial time algorithms. Feige (1998) improved this lower bound to ${\bigl (}1-o(1){\bigr )}\cdot \ln {n}$ under the same assumptions, which essentially matches the approximation ratio achieved by the greedy algorithm. Template:Harvtxt established a lower bound of $c\cdot \ln {n}$ , where $c$ is a constant, under the weaker assumption that P$\not =$ NP. A similar result with a higher value of $c$ was recently proved by Template:Harvtxt.