Counterexample to greedy solution for set cover problem

Question

I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows:

1-6. The set cover problem is as follows: given a set of subsets $S_1,\dots,S_m$ of the universal set $U = \{1,\dots,n\}$, find the smallest subset of $T \subset S$ subsets such that $\cup_{t_i \in T} t_i = U$. For example, there are the following subsets, $S_1 = \{1,3,5\}$, $S_2 = \{2,4\}$, $S_3 = \{1,4\}$, and $S_4 = \{2,5\}$. The set cover would then be $S_1$ and $S_2$.

Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.

My answer is as follows:

$S = \{\{1, 2\}, \{3, 4\}, \{2, 5\}, \{5\}\}$, $U=\{1,2,3,4,5\}$.

The algorithm will use the following sets: $\{\{1, 2\}, \{3, 4\}, \{2, 5\}\}$, while {{1, 2}, {3, 4}, {5}}$. would be more minimal.

Do you think its correct? I assume here that algorithm minimizes number of uncovered elements in each iteration and not the entire size of set to choose – that's why it might choose $\{2,5\}$ instead of $\{5\}$.

I have found this answer online:

One counter-example consists of a series of subsets that increases in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:

$S_1 = \{1,2\}$


$S_2 = \{3,4,5,6\}$


$S_3 = \{7,8,9,10,11,12,13,14,15,16\}$


$S_4 = \{1,2,3,4,5,6,7,8\}$

$
S_5 = \{9,10,11,12,13,14,15,16\}$

The greedy algorithm will choose $S_3,S_2,S_1$, while the optimal solution is simply $S_4,S_5$.

My understanding is that the algorithm would choose $S_3,S_4$ and not $S_3,S_2,S_1$, since $S_4$ has more uncovered elements than $S_2$.

Answer 1

Usually the set cover problem is formulated such that the quantity to be minimized is the number of sets one picks rather than the sum of the numbers of elements of the sets picked. Unfortunately, this means that your example does not prove that the given greedy algorithm fails to find optimal solutions as the cover it produces consists of 3 sets, which is minimal for your instance.

A valid (and perhaps minimal?) counterexample would be $\mathcal U = \{1, 2, 3, 4, 5, 6\}$ with $\mathcal S =\{\{1, 2, 3\}, \{4, 5, 6\}, \{2, 3, 4, 5\}\}$, which works similarly to the one you found. The minimal cover consists only of the first two sets (these two must be in every cover since there is no other way to account for $1$ and $6$ otherwise) whereas the greedy algorithm will choose the last set first (since it covers 4 rather than 3 elements) and hence picks all sets, leading to a cover of size 3 which is not optimal.