Question

8. The problem 'SET COVER gives two numbers n, k, and a family of n subsets of (,.. n It asks whether it is possible to select k of these subsets such that each number in (1,... ,n) occurs in at least one of the selected subsets. (8.1) Show that the problem 'SET COVER' is in the class NP (8.2) The simplest algorithm to solve set cover just tests all the possible choices of k subsets. How long will that take?

Algorithms

Answer 1

8.1 SET COVER problem is in class NP because this problem belongs to the class of decision problem with "yes" or "no" answer and if the answer is "yes" on some input instance, then the solution proposed can be verified in polynomial time to the size of the input and size of the solution. Below is the polynomial time verifier, which given the number n and k and the set of subsets S1, S2,...,Sk , check whether union of all these subset is the set S = {1,2,...,n}.

Verify_SET_COVER(S , Solution_Set , n , k) //when S = {1,2,..,n} and Solution_Set = {S1,S2,...,Sk}

1. If |Solution_Set| != k then return FALSE //since there are not k subsets in the solution

2. Union = EMPTY //This set will take union of all the subsets in the solution

3. For every subset Si in Solution_Set :-

4........Union = Union U { Si } //Union will cover all the elements of Si

5. If Union == S then return TRUE //Since this means union of all subsets is equal to set S = {1,2,...,n}

6. else Return FALSE  

Since polynomial time verifier exist for the above problem, hence SET COVER problem belongs to kclass NP.

8.2 Since total number of ways of selecting k subsets output of n subsets is $\binom{n}{k} = \frac{n!}{k!(n-k)!}$

And then to test whether the union of k subsets is equal to set S will take O(kn) time, so total time complexity will be $O \left (nk\binom{n}{k} \right )$ .

Please comment for any clarification.