Reference no: EM132122266

Remember all of the following steps when showing that a problem D is NPcomplete:

1. Show that D is in NP by briefly explaining how to quickly verify a solution to it.

2. Choose another problem Q that is known to be NP-hard (one that we showed in class) and explain how you convert an instance of that problem into an instance of D (this is to show that D is NP-hard).

3. Explain why a yes-instance of Q gets turned into a yes-instance of D.

4. Explain why a no-instance of Q gets turned into a no-instance of D.

Consider the following problem SELECT SET: the input is a list of sets S and an integer k, and the problem is, can you choose k elements such that every set in the list S contains at least one of those elements?

For example, given S = (1, 3),(2, 3, 4),(3, 4, 6, 9),(5, 6), and k = 3, we could pick 3, 4, and 6 as the k elements, and all of the sets in S contain either 3, 4, or 6, so this would be a yes-instance of SELECT SET. Prove that SELECT SET is NP-complete.