17.3. Dominating Set and Set Cover*

The main result we will prove in this section is a solution of the set cover problem:

Theorem 17.5: Let \((U,\mathcal{S})\) be an instance of the set cover problem. Then an optimal set cover of \(U\) can be computed in \(O^*\bigl(1.24^{|U| + |\mathcal{S}|}\bigr)\) time.

We can use Theorem 17.5 to solve the dominating set problem:

A dominating set of a graph \(G = (V, E)\) is a subset \(D \subseteq V\) such that every vertex in \(V \setminus D\) hsa a neighbour in \(D\).

Dominating Set Problem: Given a graph \(G = (V, E)\), find a dominating set of minimum size.

Corollary 17.6: A minimum dominating set of a graph can be found in \(O^*(1.53^n)\) time.

Proof: Let \(U = V\) and let \(\mathcal{S} = \{N[v] \mid v \in V\}\). Then \(D\) is a dominating set of \(G\) if and only if \(\{N[v] \mid v \in D\}\) is a set cover of \(U\). Thus, we can find a minimum dominating set of \(G\) by finding a minimum set cover of \(U\) using subsets of \(\mathcal{S}\). Since \(|U| = n\) and \(|\mathcal{S}| = n\), this takes \(O^*\bigl(1.24^{2n}\bigr) = O^*(1.53^n)\) time, by Theorem 17.5. ▨

Note that Corollary 17.6 improves significantly on the naïve \(O^*(2^n)\)-time algorithm that simply tries all possible subsets of the vertices of \(G\). A simple analysis of the algorithm discussed in this section based only on the input size of each recursive call produces a running time bound of \(O^*(1.91^n)\). Measure and Conquer allows us to significantly improve on this bound and thereby obtain Corollary 17.6.