Exercise 6 (2 bonus points). Suppose that you have a subroutine that solves ILP (integer linear programming). How can you use this subroutine to solve MAXIMUM CLIQUE? More exactly, give a polynomial-time algorithm that transforms a graph G into an integer linear program P such that an optimal solution to P induces a maximum-size clique in G. Apply Figure 5: Instance of MAXIMUM CLIQUE for Exercise 6 your algorithm to the graph in Fiqure 5. What program P is obtained? Hint. If G has vertices 1,2,... ,n, use variables r1,..., Xn with the meaning: x1 if vertex i belongs to the clique and xi 0 otherwise