1 [10 marks] The point of this question is to prove that if there is a polynomial-time constant- factor approximation algorithm for the Maximum Clique problem then there is a PTAS Recall that the Maximum Clique problem (as an optimization problem) is to find the largest subset C of vertices such that every pair of vertices in C is joined by an edge in the graph (a) [4] For a graph G = (V,E) on n vertices define the k-th power of G, denoted G, as follows. The vertex set of G consists of the k-tuples (vi, v2,.. . , vk) where v; E V. Note that Gk has nk vertices. There is an edge between (vi, 12, , vx) and (w1,/2,..., wk) if and only if for al i -1.k, either v- wi or there is an edge (vi, wi) in G. (You will understand this better by making some small examples.) Prove that G has a clique of size t if and only if Gk has a clique of size t*. (b) 6 Suppose there is a 1-approximation algorithm A for the Maximum Clique problem that runs in time O(p(n)) where n is the number of vertices of the input graph and p is a polynomial function. Using part (a) and algorithm A, give a PTAS for the Maximum Clique problem. The input for your PTAS will be a graph G on n vertices and a value > 0. What is the run-time of your PTAS, in terms of n, e and p( )? (In fact, your argument will work for any constant-factor approximation.) 1 [10 marks] The point of this question is to prove that if there is a polynomial-time constant- factor approximation algorithm for the Maximum Clique problem then there is a PTAS Recall that the Maximum Clique problem (as an optimization problem) is to find the largest subset C of vertices such that every pair of vertices in C is joined by an edge in the graph (a) [4] For a graph G = (V,E) on n vertices define the k-th power of G, denoted G, as follows. The vertex set of G consists of the k-tuples (vi, v2,.. . , vk) where v; E V. Note that Gk has nk vertices. There is an edge between (vi, 12, , vx) and (w1,/2,..., wk) if and only if for al i -1.k, either v- wi or there is an edge (vi, wi) in G. (You will understand this better by making some small examples.) Prove that G has a clique of size t if and only if Gk has a clique of size t*. (b) 6 Suppose there is a 1-approximation algorithm A for the Maximum Clique problem that runs in time O(p(n)) where n is the number of vertices of the input graph and p is a polynomial function. Using part (a) and algorithm A, give a PTAS for the Maximum Clique problem. The input for your PTAS will be a graph G on n vertices and a value > 0. What is the run-time of your PTAS, in terms of n, e and p( )? (In fact, your argument will work for any constant-factor approximation.)
