We start by defining the Independent Set problem. Given a graph G = (V, E), we s
ID: 3028629 • Letter: W
Question
We start by defining the Independent Set problem. Given a graph G = (V, E), we say a set of nodes S V is independent if no two nodes in S are joined by an edge. The Independent Set problem, which we denote IS, is the following. Given G, find an independent set that is as large as possible. Stated as a derision problem, IS answers the question, does there exist a set .S elementof G such that |S| k? Then set K as large as possible. For this problem, you may take as given that IS is NP-complete. A store trying to analyze the behavior of its customers will often maintain a table. A where the rows of the table correspond to the customers and the columns (or fields) correspond to products the store sells. The entry A[i, j] specifies the quantity of product j that has been purchased by customer i. For example. Table ?? shows one such table. One thing that a store might want to do with this data is the following. Let's say that a subset S of the customers is diverse if no two of the customers in S have ever bought the same product (i.e., for each product, at most one of the customer in S has ever bought it). A diverse set of customers can be useful, for example, as a target pool for market research. We can now define the Diverse Subset problem (DS) as follows: Given an m times n array A as defined above and a number k lessthanorequalto m, is there a subset of at least k customers that is diverse? Prove that DS is NP-complete.Explanation / Answer
Diverse Subset Problem is NP: Given a set of k customers, it can be checked in polynomial time that no two customers in the set have ever bought the same product.
Independent Set is known to be NP-complete.
Independent Set P Diverse Subset Problem: Suppose we have a black box for Diverse Subset Problem and want to solve an instance of Independent Set. For our Independent Set Problem, we have a graph G=(V,E) and a number k, and need to find out if G contains an independent set of size (at least) k. We need to reduce the Independent Set Problem to a Diverse Subset Problem. We do this by constructing an array where each v in V is a customer and each e in E is a product, and customer v purchased every product e for which the product edge e touches the customer node v. Then we ask the black box for the Diverse Subset Problem if there is a subset of k customers that is diverse.
The black box for the Diverse Subset Problem will return “Yes” the Independent Set Problem is “Yes”, i.e. graph G contains an independent set of size k.
The black box for the Diverse Subset Problem will return “Yes”: there is a subset of k customers that is diverse, no two customers in the subset have ever bought the same product. Then in the graph that can be constructed from this, no two customer nodes in the diverse subset share an edge, so it is an independent set of size k.
The Independent Set Problem is “Yes”, i.e. graph G contains an independent set of size k. Then in the corresponding array, the independent set of size k corresponds to a set of customers where only one customer has purchased each product, so there is a diverse subset of size k
Independent Set Problem requires polynomial time to construct the problem as a Diverse Subset Problem and polynomial calls to the Diverse Subset Problem black box. Hence, Independent Set P Diverse Subset Problem.
If Y is an NP-complete problem, and X is a problem in NP with the property that Y P X, then X is NP-complete.
Thus, Diverse Subset Problem is NP-complete.
-----------------------------
DO THUMBS UP ^_^
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.