An instance of $M$ is a collection of sets $S_1, \dots, S_m$ and a bound $B$. A solution is a set $T$ containing $B$ distinct items, such that

  1. each item in $T$ belongs to some $S_i$, and
  2. each $S_i$ contains at most one item in $T$.

Show that $M$ is NP-complete by giving a reduction $\mathrm{IS} \to M$

Any help on how to start would be appreciated!

  • 3
    $\begingroup$ What have you tried and where did you get stuck? Hint: check out our reference question (some might say this is a duplicate). Or, in case you are in the mood for more googling than thinking, note that this is a well-known problem. $\endgroup$ – Raphael Dec 8 '14 at 18:29

You have to demonstrate that you can convert all instances of the decision problem of independent set to your problem, and then you have to prove that the independent set problem can only be solved if you can solve your problem about sets.

The decision problem of independent set is determining if an undirected graph contains an independent set with a number K of vertex.

To do that, you can start by labeling the vertex of every graph with numbers, like this:

graph with numbers

It, doesn't matter if the numbers are in order or not, the only thing that matters is that you can number them with a unique numbering (no vertex share a number in the graph).

Then, you have to create the set of sets with the numbers of the labels of the vertex of the graph. If you create the set of sets in the correct way, you will have reduced independent set to your problem.

Good luck



Then you have to create a set with the label of the number of each vertex $v_i$ and every neighbour of that vertex. For the graph avobe you had something like $\{1,4\}$ $\{2,4\}$ $\{3,4\}$ $\{4,5\}$ and $\{5,6\}$ So if you can pick $B$ disctint elements according to the rules of your problem, that will mean that there exist an independent set of size at least $B$ on the graph


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.