17.3.1. The Algorithm

The algorithm we use to solve the set cover problem is rather simple. Given an input \((U,\mathcal{S})\), we assume that \(\bigcup_{S \in \mathcal{S}} S = U\) because otherwise there is no solution or some sets in \(\mathcal{S}\) contain "useless" elements not contained in \(U\). If this assumption is satisfied for the initial input, then the recursive calls the algorithm makes ensure that it is satisfied also for all recursive calls the algorithm makes.

Given an input \((U,\mathcal{S})\), the algorithm considers the following 6 rules and uses the first rule that is applicable to this input:

1. If \(U = \emptyset\), then return \(\emptyset\). Clearly, no sets are needed to cover the elements in \(U\).

2. If there exist two sets \(S_1, S_2 \in \mathcal{S}\) such that \(S_1 \subseteq S_2\), then any set cover \(\mathcal{C}\) with \(S_1 \in \mathcal{C}\) has a corresponding set cover \(\mathcal{C}' = \mathcal{C} \setminus \{S_1\} \cup \{S_2\}\) of at most the same size. Thus, there exists an optimal set cover of \(U\) using only sets in \(\mathcal{S} \setminus \{S_1\}\). We make one recursive call on the input \((U, \mathcal{S} \setminus \{S_1\})\) and return its answer.

3. If there exists an element \(e \in U\) that belongs to exactly one set \(S \in \mathcal{S}\), then \(S\) must be part of any set cover of \(U\). Adding \(S\) to a set cover \(\mathcal{C}\) covers all elements in \(S\) and the remaining elements of \(\mathcal{C}\) only need to cover the elements in \(U \setminus S\). Thus, we make one recursive call on the input \((U \setminus S, \mathcal{S} - S)\), where \(\mathcal{S} - S = \{S' \setminus S \mid S' \in \mathcal{S} \setminus \{S\}\}\), to compute a set cover \(\mathcal{C}'\) of \(U \setminus S\) using sets in \(\mathcal{S} - S\). We return the set \(\mathcal{C} \cup \{S\}\), where \(\mathcal{C}\) is the collection of sets in \(\mathcal{S}\) corresponding to the sets in \(\mathcal{S} - S\) included in \(\mathcal{C}'\).

4. If neither of the previous two rules applies, then let \(S \in \mathcal{S}\) be a set of maximum size and apply one of the following two rules:

5. If \(|S| = 2\), then the choice of \(S\) implies that all sets in \(\mathcal{S}\) have cardinality at most \(2\). Moreover, if there is a set \(S' \in \mathcal{S}\) of cardinality \(1\), then either the element \(e \in S'\) is contained only in \(S'\) or \(S'\) is a subset of another set \(S'' \in \mathcal{S}\) that also contains \(e\). In either case, one of Rules 1 or 2 would have applied. This shows that every set in \(\mathcal{S}\) has size exactly \(2\). Lemma 17.7 below shows that a minimum set cover can be found in polynomial time in this case. Thus, we compute a minimum set cover of \(U\) using sets in \(\mathcal{S}\) without making any further recursive calls in this case.

6. If \(|S| \ge 3\), then a minimum set cover of \(U\) either includes \(S\) or does not. In the former case, we need to augment \(\{S\}\) with a set cover of the elements in \(U \setminus S\). We find the smallest such set cover \(\mathcal{C}_1\) by making a recursive call on the input \((U \setminus S, \mathcal{S} - S)\). In the latter case, we need to cover \(U\) using sets in \(\mathcal{S} \setminus \{S\}\). We find the smallest such set cover \(\mathcal{C}_2\) by making a resursive call on the input \((U, \mathcal{S} \setminus \{S\})\). We return the smaller of \(\mathcal{C}_1 \cup \{S\}\) and \(\mathcal{C}_2\).

Observe that Rule 6 is the only rule of the algorithm that makes more than one recursive call. Before analyzing the branching number of this rule, we discuss how to find a minimum set cover when Rule 5 applies:

Lemma 17.7: Let \(U\) be a set and let \(\mathcal{S}\) be a collection of subsets of \(U\) of size \(2\) such that \(U = \bigcup_{S \in \mathcal{S}} S\). Then a minimum set cover \(\mathcal{C} \subseteq \mathcal{S}\) of \(U\) can be found in polynomial time.

Proof: We can model this input as a graph \(G = (U, E)\), where \(E = \{(u,v) \mid \{u,v\} \in \mathcal{S}\}\). Let \(n = |U|\) and consider a minimum set cover \(\mathcal{C} \subseteq \mathcal{S}\) of \(U\). Let us order the sets \(S_1, \ldots, S_k \in \mathcal{C}\) so that there exists an index \(1 \le h \le k\) that satisfies \(S_i \cap (S_1 \cup \cdots \cup S_{i-1}) = \emptyset\) for all \(1 \le i \le h\) and \(|S_i \cap (S_1 \cup \cdots \cup S_{i-1})| = 1\) for all \(h < i \le k\).

To see that such an ordering exists, note that \(|S_i \cap (S_1 \cup \cdots \cup S_{i-1})| \le |S_i| = 2\) for all \(1 \le i \le k\) no matter the ordering of the sets \(S_1, \ldots, S_k\) we choose. If \(|S_i \cap (S_1 \cup \cdots \cup S_{i-1})| = |S_i|\), then \(S_i \subseteq S_1 \cup \cdots \cup S_{i-1}\). Thus, \(\mathcal{C} \setminus \{S_i\}\) is a set cover of \(U\), a contradiction. Therefore, \(|S_i \cap (S_1 \cup \cdots \cup S_{i-1})| \le 1\) for all \(1 \le i \le k\), again no matter the ordering of the sets \(S_1, \ldots, S_k\) we choose.

We can therefore construct the desired ordering as follows: Start by picking \(S_1\) arbitrarily. After choosing the first \(i-1\) sets \(S_1, \ldots, S_{i-1}\), pick an arbitrary set \(S_i \in \mathcal{C} \setminus \{S_1, \ldots, S_{i-1}\}\) such that \(S_i \cap (S_1 \cup \cdots \cup S_{i-1}) = \emptyset\) if such a set exists. Otherwise, choose \(S_i\) arbitrarily from \(\mathcal{C} \setminus \{S_1, \ldots, S_{i-1}\}\). Let \(h\) be the smallest index such that \(h = k\) or \(S_{h+1} \cap (S_1 \cup \cdots \cup S_h) \ne \emptyset\). Then clearly \(S_i \cap (S_1 \cup \cdots \cup S_{i-1}) = \emptyset\) for all \(1 \le i \le h\). By the choice of \(S_{h+1}\), we have \(S_i \cap (S_1 \cup \cdots \cup S_{i-1}) \supseteq S_i \cap (S_1 \cup \cdots \cup S_h) \ne \emptyset\) for all \(h < i \le k\). Since \(|S_i \cap (S_1 \cup \cdots \cup S_{i-1})| \le 1\), we thus have \(|S_i \cap (S_1 \cup \cdots \cup S_{i-1})| = 1\) for all \(h < i \le k\).

Now let \(e_i = (u, v)\) be the edge in \(G\) corresponding to the set \(S_i = \{u, v\}\), for all \(1 \le i \le k\). Then \(\{e_1, \ldots, e_h\}\) is a matching of \(G\) and every edge \(e_i\) with \(h < i \le k\) covers exactly one vertex not covered by the edges \(e_1, \ldots, e_{i-1}\). This gives \(n = 2h + (k - h) = k + h\) or \(|\mathcal{C}| = k = n - h\). Since \(\{e_1, \ldots, e_h\}\) is a matching of \(G\), this shows that \(|\mathcal{C}| \ge n - |M|\), where \(M\) is a maximum matching of \(G\).

Conversely, for a maximum matching \(M\) of \(G\), let \(F = M \cup F'\), where \(F'\) contains an arbitrary edge incident to each vertex not covered by \(M\). Then \(|F| = |M| + (n - 2|M|) = n - |M|\). Since the collection of sets corresponding to the edges in \(F\) is a set cover of \(U\), we have \(|\mathcal{C}| \le n - |M|\). Together with the previous bound \(|\mathcal{C}| \ge n - |M|\), we obtain that \(|\mathcal{C}| = n - |M|\).

This shows that we can find a minimum set cover \(\mathcal{C} \subseteq \mathcal{S}\) of \(U\) by computing a maximum matching \(M\) of \(G\), adding an arbitrary edge incident to each vertex not covered by \(M\) to \(M\), and then returning the collection of sets in \(\mathcal{S}\) corresponding to the chosen edges. Since a maximum matching in an arbitrary graph can be found in polynomial time, a minimum set cover \(\mathcal{C} \subseteq \mathcal{S}\) can be found in polynomial time. ▨