3. Set Cover

Acknowledgements

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

What are the fragments (AKA, what do we want to store)?

Let us try projection again. Fix a subset X \subseteq U and and an integer 0 \leqslant j \leqslant |\mathcal{F}|.

Define T[X, j] as the minimum possible size of a subset \mathcal{F}^{\prime} \subseteq\left\{F_1, F_2, \ldots, F_j\right\} that covers X.

The T’s will be our fragments.

Are the fragments going to be useful (AKA, where is the final answer)?

By definition, T[U,m], where m := |\mathcal{F}|.

Do we have a kickstart (AKA, what are the base cases)?

Observe that T[\emptyset, 0]=0 while T[X, 0]=+\infty for X \neq \emptyset.

How do the fragments come together (AKA, how do we compute the values that we have agreed to store)?

Let X \subseteq U and 0<j \leq|\mathcal{F}|. We have that:

T[X, j]=\min \left(T[X, j-1], 1+T\left[X \backslash F_j, j-1\right]\right),

depending on whether we decide to include F_j in our solution or not. If we do, then we adjust the set of elements that need to be covered, and if we don’t, we push the full responsibility of covering X to the smaller subfamily. As usual, we pick the best of both worlds.

Can we put the pieces together without getting stuck (AKA, are the dependencies in step #4 acyclic)?

The entries can be computed by computing sets of smaller sizes before larger ones, and for sets of the same size, processing smaller indices before larger ones.

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

Correctness of the DP

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.