# Finding an instance of an n-element set cover

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?

• I'm having a hard time understanding what you are asking. You are looking for an algorithm to... do what, exactly? What are the requirements? It's not clear what you are asking for. Are you asking for an exhaustive search algorithm to find the optimal set cover? (If so, the best way to do that is probably not to modify the algorithm you showed us, but rather to start from scratch.) Would this be clear to you, if you were reading it? I suggest you proofread the question and edit it to try to explain more clearly what you want to achieve and what you've already tried.
– D.W.
Nov 24, 2013 at 5:28
• you want the algo to run in exponential time?? Nov 24, 2013 at 9:01
• @D.W. sorry for the confusion. My understanding of the problem wasnt thatvgreat to begin with. After some debate wiyh friends we've settled. On the idea thar they are asking for a set cover that has n elements in it. What really confused me about the question was that the last part about greedy set cover begin capable of returning an exponential amount of solutions. I wasn't sure why that was there. I'll that y to reorder and neaten everything up.
• Please edit to make the algorithm unambiguous. For example, is line 6 a part of the while loop? Nov 26, 2013 at 17:08
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.