There is a shop which consists of N items and there are M buyers. Each buyer wants to buy a specific set of items. However, the cost of all transactions is same irrespective of the number of items sold. So, the shopkeeper needs to maximize the number of buyers. The buyers will buy only if all the items are being sold. Items are unique. All items need not be sold.

So, basically, we have a bipartite graph. We need to find a set of edges which maximize the number of nodes on Buyer vertex set such that each node on item set has only one edge. Any suggestions?

  • $\begingroup$ Hint: Show that your problem is NP-hard by reducing from UNIQUE-3SAT (3SAT where the goal is to satisfy each clause by exactly one literal). $\endgroup$ – Yuval Filmus Mar 9 '14 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.