Set$-$Covering Problem $($SCP$)$

Given a set of elements $\{1,2,$dots,$n\}($called the universe$)$ and a collection $S$ of $m$ subsets whose union equals

the universe, the set cover problem is to identify the smallest sub$-$collection of $S_{{?}_{?}}$ whose union equals the

universe. For example, consider the universe $U=\{1,2,3,4,5\}$ and the collection of sets $,$

$\{3,4\},\{4,5\}.$ Clearly the union of $S$ is $U.$ However, we can cover all elements with only two sets: $,$

$\{4,5\},$ see picture. Therefore, the solution to the set cover problem has size $2.$

More formally, given a universe $U$ and a family $S$ of subsets of $U,$ a set cover is a subfamily CsubeS of sets

whose union is $U.$ In the decision version of the set$-$covering problem, the input is a pair $(U,S)$ and an

integer $k$; the question is whether there is a set cover of size $k$ or less. This problem has been proven to be NP$-$

complete, meaning that there is no known polynomial time solution.

Solutions to this problem have a number of application areas such as vertex cover or edge cover in graph theory.

As a result, several greedy algorithms have been proposed for the polynomial time approximation of set

covering. One such strategy is to interactively choose the set that contains the largest number of uncovered

elements. The detailed algorithm can be found in $($Chvatal$,1979)-$ see the reference below.

Questions:

Show a case study that the greedy algorithm above finds the optimal set cover in polynomial time given

$k=3.(1$ point$)$

Show a case study that the greedy algorithm does not find the optimal set cover in polynomial time

given $k=3.(1$ point$)$

What is the complexity of this greedy algorithm? Does it rely on the initial ordering of the subsets?

Show your analysis. $(2$ points$)$