3. Set Cover
Much of the material in this section is borrowed from Chapter 6 in Parameterized Algorithms.
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)}.
Proof of Correctness
Theorem. Given a SET COVER instance (U, \mathcal{F}, k), the minimum possible size of a subfamily \mathcal{F}^{\prime} \subseteq \mathcal{F} that covers U can be found in time 2^{|U|}(|U|+|\mathcal{F}|)^{\mathcal{O}(1)}.
Proof. Let \mathcal{F}=\left\{F_1, F_2, \ldots, F_{|\mathcal{F}|}\right\}. We prove the correctness of the recurrence by showing inequalities in both directions.
In one direction, let \mathcal{F}^{\prime} \subseteq\left\{\overline{F_1}, F_2, \ldots, F_j\right\} be a family of minimum size that covers X. We distinguish two cases. If F_j \notin \mathcal{F}^{\prime}, then note that \mathcal{F}^{\prime} is also a valid candidate for the entry T[X, j-1] (i.e., \mathcal{F}^{\prime} \subseteq\left\{F_1, F_2, \ldots, F_{j-1}\right\} and \mathcal{F}^{\prime} covers X ). If F_j \in \mathcal{F}^{\prime}, then \mathcal{F}^{\prime} \backslash\left\{F_j\right\} is a valid candidate for the entry T\left[X \backslash F_j, j-1\right].
In the other direction, observe that any valid candidate \mathcal{F}^{\prime} for the entry T[X, j-1] is also a valid candidate for T[X, j] and, moreover, for every valid candidate \mathcal{F}^{\prime} for T\left[X \backslash F_j, j-1\right], the family \mathcal{F}^{\prime} \cup\left\{F_j\right\} is a valid candidate for T[X, j].
This completes the proof.