# Reducing Independent Set to a problem to prove that it is NP complete

Given:

• A set of available customers $$c_1, c_2, \dots, c_n$$.
• A set of available foods $$f_1, f_2, \dots, f_m$$.
• Each customer will choose a subset of the available food.

Problem:

• Find the maximum number of customers that can be chosen, such that no two customers share the same food.

Question:

• How to reduce the independent set problem to this problem, in order to prove that this is an NP-Complete problem ?
• What have you tried? Where did you get stuck? – dkaeae Dec 6 '18 at 14:02