Constrained Knapsack without weight

Question

I just came across the following problem(it reminds me of the knapsack-problem, but there a some differences):

You are given a number n of items which you have to put inside your knapsack with a maximum profit. Each item has a specific profit value and a specific shape. Because of their shape, some items cannot be put into the knapsack together. Unlike the normal knapsack-problem there is no maximum weight that limits the number of items in the knapsack. You are also given a list for each item. In that list you can see the items that can be put into the knapsack with the corresponding item.

Is there an algorithm that calculates the optimum solution? Or is it an NP-complete problem? In that case, is there a method of approximation?

Answer 1

I think that this is NPC.

The polynomial verification requirement is trivial.

The reduction is to the Maximal Independent Set problem. For each MIS instance G = (V, E), construct a set of items V with unit profit each. For each item v ∈ V, the list of items with which it can be placed is the set of vertices to which it doesn't share an edge. I.e., if G(v) is the list of items that can go with v, then G(v) = {w | (u, w) ∉ E}.

If there is a solution with profit k for the new problem, then it uses k items that are not in each other's lists. It follows that there is a solution of size k to the independent set problem.