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 A+1-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. 3: 1: function FIND-IND-SET(G = (V, E)) 2: Sk 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} returns 4: 5: 7: 1 (a) Show that the above algorithm is in fact a Ati-approximation in expectation for MAX-INDEPENDENT-SET. That is, the expected size of the output cut is at least Ati times the size of the maximal independent set. (Hint: use linearity of expectation to show that, in expectation, Ati 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 times the size of the maximal independent set. (Hint: use linearity of expectation to show that, in expectation, Ati 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 A+1-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. 3: 1: function FIND-IND-SET(G = (V, E)) 2: Sk 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} returns 4: 5: 7: 1 (a) Show that the above algorithm is in fact a Ati-approximation in expectation for MAX-INDEPENDENT-SET. That is, the expected size of the output cut is at least Ati times the size of the maximal independent set. (Hint: use linearity of expectation to show that, in expectation, Ati 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 times the size of the maximal independent set. (Hint: use linearity of expectation to show that, in expectation, Ati 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