4. Algorithms and Complexity (25 marks) (a) Consider the Clique problem in undirected graphs. Show polynomial time reduction from 3-CNF problem to Clique problem. What does this reduction show? (5 marks) (b) Does an absolute approximation algorithm exist for the Clique optimisation problem? Justify your answer. (5 marks) (c) Recall the All-Pairs Shortest Paths Problem. Input: An n x n matrix W in which W[i,j] is the weight of the edge from i to j in a graph. We require that W[i, i] = 0 for all i, and that w[i,j] = o if there is no edge from i to j. We also require that there are no negative-weight cycles in the weighted digraph corresponding to W. Output: An nx n matrix in which an element [i,j] contains the weight of a shortest (smallest-weight) path from i to j. Let D[m, i,j] be the minimum weight of any path from a node i to a node ; that contains at most m edges. How to calculate D[m, i, j] value if D[m - 1,1,j] is known for all i,j? How many steps would be needed to compute D[m,i,j] for all i, j in this case. (5 marks) (d) In the multiprocessor scheduling problem the input consists of n jobs, Jh,..., Jn. Job J; has a corresponding runtime p; (a rational number). The jobs are to be distributed between m identical machines The finish-time is the maximum, over machines M, of the total runtime of jobs assigned to M. The goal is to minimise the finish-time. In the following greedy approximation algorithm we consider the n jobs one-by-one: When a job is considered, pick the currently least-loaded machine, and assign the job to that machine. What is the "relative performance of this algorithm"? Construct an instance of the prob- lem on which the algorithm will have the worse performance. (5 marks) (e) The approximation algorithm A that uses the fact that every planar graph has a vertex of degree at most 5 takes as input a planar graph G and returns a proper colouring o of G using at most 5 colours. Thus, the absolute error of this algorithm is D(G, A(G)) = v(G, A(G)) - v*(G)