Imagine that you are a Hollywood movie producer who is trying to decide how your new movie
Question:
Imagine that you are a Hollywood movie producer who is trying to decide how your new movie should end. To help you make this decision, you would like to assemble a group of movie-goers together to do a focus group. To avoid biases, you have asked that the group be selected so that no two people in the group has previously seen the same movie. So, among the set of possible focus-group members, you have asked that each one fill out a list of all the movies they have seen, and you will be using these lists to make your decision about who to invite to the focus group. Show that the decision version of the problem of finding the largest set of movie-goers for this focus group such that no two people in the group has previously seen the same movie is NP-complete.
Step by Step Answer:
Algorithm Design And Applications
ISBN: 9781118335918
1st Edition
Authors: Michael T. Goodrich, Roberto Tamassia