As its name suggests, the MAX-INDEPENDENT-SET problem concerns finding the maximal independent set in a given graph G. The following is a randomized 11-approximation for the MAX-INDEPENDENT-SET problem (where A is the maximum degree of any vertex in the graph). Note that this is not a constant factor approximation since A depends on the graph. 2: 3: 1: function FIND-IND-SET(G = (V, E)) S while V+ do Choose a v eV uniformly at random and remove it from V if v does not share an edge with any vertex in S then 6: SSU{v} return S 4: 5: 7: (a) Show that the above algorithm is in fact a ti-approximation in erpectation for MAX-INDEPENDENT-SET. That is, the expected size of the output cut is at least 71 times the size of the maximal independent set. (Hint: use linearity of expectation to show that, in expectation, 21 of the vertices in the graph are in S.) (b) Argue that, for any graph G = (V, E), there exists an independent set of size at least VI A+1 As its name suggests, the MAX-INDEPENDENT-SET problem concerns finding the maximal independent set in a given graph G. The following is a randomized 11-approximation for the MAX-INDEPENDENT-SET problem (where A is the maximum degree of any vertex in the graph). Note that this is not a constant factor approximation since A depends on the graph. 2: 3: 1: function FIND-IND-SET(G = (V, E)) S while V+ do Choose a v eV uniformly at random and remove it from V if v does not share an edge with any vertex in S then 6: SSU{v} return S 4: 5: 7: (a) Show that the above algorithm is in fact a ti-approximation in erpectation for MAX-INDEPENDENT-SET. That is, the expected size of the output cut is at least 71 times the size of the maximal independent set. (Hint: use linearity of expectation to show that, in expectation, 21 of the vertices in the graph are in S.) (b) Argue that, for any graph G = (V, E), there exists an independent set of size at least VI A+1