Finding an instance of an n-element set cover

Question

Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter line 3 so that it would run until the size of C was equal to n, and change the logic in line 4 so that it would pick and remove vertices until the size of n. A vertex would be removed when the size of C doesn't equal to n but the cover is complete. I can't really think of any other way to do it. The real problem is that I'm not entirely sure how to make the algorithm run in exponential time like they are asking.

GREEDY-SET-COVER can return a number of different solutions, depending on how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE.n/ that returns an n-element instance of the set-covering problem for which, depending on how we break ties in line 4, GREEDY-SET-COVER can return a number of different solutions that is exponential in n.

$X$ — some finite set
$F$ — a family of subsets of $X$
$C$ — cover being constructed

GREEDY-SET-COVER($n$)
1 let $U = X$
2 let $C = \varnothing$
3 while $U \ne \varnothing$
3a select an $S \in F$ that maximizes $\left|S \cap U\right|$
3b set $U = U \setminus S$
3c set $C = C \cup \{S\}$
4 return $C$

Could it be said that since the number of subsets a set has is $2^n$ and that in the worst case this algorithm will end up finding all of those subsets before settling on an n-instance set to return?

Answer 1

I think you are being confused by the way the question is phrased. The question asks for a sequence of instances $I_n$, consisting of triples $\langle X_n,F_n \rangle$, such that $|X_n| = n$ and GREEDY-SET-COVER$(X_n,F_n)$ could have $C^n$ many results, for some constant $C>1$. These results come from the fact that at step 4 there could be many sets that are eligible.

For some reason, the question asks you for an algorithm which generates the sequence: given $n$, it should output $\langle X_n,F_n \rangle$. Since the instances you are going to construct will be pretty simple, you should have no problem writing an algorithm that generates them, but in fact no one cares about this algorithm; the point is only that these "bad" instances exist (they're not actually bad, mind you).

The easiest way to construct these instances is to use a gadget, say $F_3 = \{(1,2),(1,3),(2,3)\}$. You can check that running the greedy algorithm can result in three different covers. I'll let you continue from here.