1. Given a graph, an independent set, is a collection of nodes which have no edges among them. Thus, in the following graph,
the nodes B, D, and E form an independent set because there are no edges connecting one of them to the other two.
Prove that the problem Given a graph, does it contain an independent set of K nodes? is NP-Complete. There are two steps to the proof. First show that it is an NP problem.
Second, show that a known NP-Complete problem reduces to it. That is, show that a known NP-Complete problem can be changed to an IND_SET problem in such a manner to the two problems give the same answer for their respective inputs. You also need to show that this transformation can be done in time that is polynomial in the size of the input.
Note that we have shown 3 problems to be NP-Complete: SAT, CLIQUE, and VERTEX_COVER. One of these problems can easily be reduced to IND_SET.
Show that IND_SET is in NP.
Show that a known NP-Complete problem can be transformed to an IND_SET
problem.
Show that this transformation can be done in time that is polynomial in the size of
the input.
Show that the two problems give the same answer for their respective inputs.