An n X n grid is an undirected graph G with n$\text{'}$ vertice, consisting of n rows and n columns of vertices. io$,$ all vertices have exactly four neighbors, except for the boundary vertices $($the four comer vertices lave two neighbors, the other boundary vertices have three neighbors$).$ Each vertex v has a non$-$egative integer weight w$($v$),$ and all weights are distinct. Our goal is to compute an independent set s f vertices, so that the sum of the weights of the vertices in $5$ is as large as possible.$)115$ points$]$ This is an optimization problem. What is the decision version of this problem? Prove that this decision version is in NP$.)110$ points$]$ Now consider the following greedy algorithm for this problem: unction GreedyIndependentSet $($G$)$tart with S :$=$hile some node remains in G doPick a node v of maximum weightAdd v to SDelete v and its neighbors from Geturn Srove that GreedyIndependentSet is a $4-$approximation algorithm.