# Why is this NP complete?

I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image:

Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each item i, and then see for each person b $$\neq$$ a if b has bought item i, then conclude that a and b cannot be diverse? And if we get through all items and no item that a has bought has been bought by b therefore implies they're diverse? Then we do this with each customer. What's wrong with this approach?

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources!
– Raphael
Nov 28 '18 at 22:47
• The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you!
– Raphael
Nov 28 '18 at 22:48
• Hint, $k$ could be something like $m/4$. Your brute force searching may run exponential steps. Nov 29 '18 at 4:45

The algorithm you described isn't polynomial time because it has to consider every possible subset of customers (they are $$2^m$$ of these).
HINT: To do the reduction, consider how you would model $$A$$ as a graph and vice-versa. Once you've done that, consider how a "diverse set" is related to a vertex cover in the graphs.