$(30$ points$)$ Given a graph G $=($V$,$ E$),$ a set of vertices D $$ V is an independent set if there are no i$,$j in D with i$,$j in E$.$ Given a graph G $=($V$,$ E$)$ with a function w:V $->$R that associates a weight to each vertex, the maximum weight independent set problem consists of finding an independent set with the maximum total weight. The decision version of this problem is an NP$-$complete problem.

a$)$ Propose a greedy algorithm for this problem. What is the computational complexity of the proposed algorithm?

b$)$ Propose a local search algorithm for this problem.

c$)$ Is the operator on which the local search algorithm proposed in the previous point is based connected?