An independent set in a graph is a set of vertices S⊆V that contains no edge (so no pair of neighboring vertices is included). The max independent set problem is to find an independent set of maximum size in a graph G. (a) Write the max independent set problem as an integer linear program. (b) Write an LP relaxation for the max independent set problem. (c) Construct an example (a family of graphs) to show that the ratio LP-OPT / OPT can be at least cn where c>0 is some absolute constant and n is the number of vertices of the graph. (d) What is the (exact) relation between the size of a max independent set and the size of min vertex cover of a graph? (e) Using this relation, what does the 2-approximation algorithm for vertex cover imply for an approximation algorithm for max independent set?