# 3. Set Cover

### The Problem

Let \mathcal{F} be a family of sets over a universe U. For a subfamily \mathcal{F}^{\prime} \subseteq \mathcal{F} and a subset U^{\prime} \subseteq U, we say that \mathcal{F}^{\prime} covers U^{\prime} if every element of U^{\prime} belongs to some set of \mathcal{F}^{\prime}.

The Set Cover problem is the following:

- The input is a family of sets \mathcal{F} over a universe U and a positive integer k.
- The task is to check whether there exists a subfamily \mathcal{F}^{\prime} \subseteq \mathcal{F} of size at most k such that \mathcal{F}^{\prime} covers U.

We describe here a algorithm for Set Cover that runs in time 2^{|U|}(|U|+|\mathcal{F}|)^{\mathcal{O}(1)}. In fact, this algorithm does not use the value of k, and finds the minimum possible cardinality of a family \mathcal{F}^{\prime} \subseteq \mathcal{F} that covers U.

### The Solution

### Analysis of Running Time

By using the recurrence, we compute all values T[X, j] for X \subseteq U and 0 \leqslant j \leqslant |\mathcal{F}|. The running time is therefore 2^{|U|}(|U|+|\mathcal{F}|)^{\mathcal{O}(1)}.