Could you do my homework?

CS 345: Spring 2015 page 1 Assignment 3

CS 345: Spring, 2015 Assignment 3 Due: 5/13/2015

Total = 20 points

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.

5 points: Show that IND_SET is in NP.

5 points: Show that a known NP-Complete problem can be transformed to an IND_SET

problem.

5 points: Show that this transformation can be done in time that is polynomial in the size of

the input.

5 points: Show that the two problems give the same answer for their respective inputs.