Proof of np-completeness

1
votes

Show that the following problem is NP-complete.

The tv problem is to select tv shows for a weekly tv night so that everyone in a group of people sees something that they like. You are given a list of people (P1, . . . , Pn) in the group and a list of possible shows (S1, . . . , Sk). For each show Si, there is a subset of the people who would like that show choice. You also get w, the number of weeks for which you can select shows. The question is whether there are these many movies so that every person likes at least one of them.

I can't figure out which np problem can be reduced to this and how to establish the certificate.

2
algorithmcomputer-sciencenpnp-complete
What is not working with your attempt? – Willem Van Onsem
I am not able to figure out which np problem can be reduced to this problem? – Ching Ling
there are a lot of problems (like SAT, TSP, ...), at least you have tried one reduction that turned out unsuccessful I think? – Willem Van Onsem
That is where I'm failing I think. I have tried using the Traveling Salesman problem and the k-Clique problem, but I can't seem to develop the 'link' between the two problems, and how they can be reduced to the mentioned problem – Ching Ling
I have looked at several examples of the proofs on MIT's open course on algorithms. However, those problems are somewhat similar to the problems that were reduced. I have also been following the Cormen/Rivest book on algorithms and the examples given there. Same problem. I haven't been able to develop the intuition behind doing these proofs and how to relate it to another already known np problem. – Ching Ling

2 Answers

1
votes

You can model this as the Set cover problem. You have elements {P1, ..., Pn}, and k subsets of these, T1, ..., Tk, defined as Ti = {Pj : Pj likes Si}. You then want to find the smallest collection of subsets such that their union is the whole set of people. Deciding whether the number of necessary subsets is less than or equal to a number is NP-complete. Finding the actual optimal collection of subsets is NP-hard.

0
votes

As Matt commented above, your problem is a set cover problem. To prove it is NP complete we must show that it is in NP, and that a known NP-complete problem can be reduced to yours. As suggested I will use Vertex Cover as our known NP-complete problem.

NP Proof

For this we need to word the problem as a decision problem and supply a certificate that can be verified in P time. Our decision problem will be can we satisfy all people using at most k shows. The certificate will be a subset of shows (we will call this subset X). To verify this certificate we need to verify:

1) X is a subset of S

This is simply done by iterating through X and verifying each item appears in S. This can be accomplished in linear time.

2) |X|<= k

This also can be solved in linear time by iterating through X incrementing a count value and comparing it to k.

3) All people are satisfied

This can be accomplished by iterating through P, and checking to see if each person is accounted for by a selection in X. In worst case where most shows cater to many people, this can be accomplished in O(P^2) time.

Since all these steps take polynomial time, the problem is in NP.

NP Complete Proof by Vertex Cover Problem Reduction

Vertex cover is a problem that concerns finding the minimum subset of vertices such that every edge has an endpoint in that subset of vertices. The input to this problem is a graph G(V,E) and k (the number of vertices). To reduce this problem to the instance of set cover you have stated above, let k = the min number of shows required to satisfy everyone, P = E, and Sn = the set of edges incident to n.

This transformation can be easily accomplished in polynomial time, as the most expensive is the last transformation (Sn = the set of edges incident to n) which takes O(V*E) time.

Now, if G has a vertex cover G' of size k, and then in our problem X is a collection of subsets representing vertices in G. This implies |X| = k. Going further, X is a set cover of P as each edge (u,v) has at least u or v in G' (as it is a vertex cover) meaning u or v are in X in our set cover problem.

What this all means is that if you represent a vertex cover problem as your problem, finding a solution also solves the transformed vertex cover problem, as each subset represents a vertex in G, and since each person is accounted for, every edge in the vertex cover problem is also accounted for