Question 2 (Parametric pruning: 10 marks) Graph clustering asks us to partition the vertex set V(G) of a graph G into subsets V,,, Vk so that some cost function of the partition is minimized or maximized. There exist many formulations of this abstract problem. Here, we consider the metric k-cluster problem. The input is a complete undirected graph G whose edge weights satisfy the triangle inequality-w(x,y) 0, unless P N that is, the 2-approximation algorithm you developed in part (a) is essentially optimal. Hint: The parametric pruning algorithm for the k-center problem and the proof that this problem cannot be (2-e)-approximated in polynomial time discussed in class exploits the relationship between the k-center problem, the dominating set problem, and maximal independent sets in the square of a graph. Use a similar strategy here, working with the metric k-cluster problem, the clique cover problem, and once again maximal independent sets. The clique cover problem asks us to find a partition of the vertex set of a graph into as few subsets Vi,..., Vk as possible such that, for each 1 0, unless P N that is, the 2-approximation algorithm you developed in part (a) is essentially optimal. Hint: The parametric pruning algorithm for the k-center problem and the proof that this problem cannot be (2-e)-approximated in polynomial time discussed in class exploits the relationship between the k-center problem, the dominating set problem, and maximal independent sets in the square of a graph. Use a similar strategy here, working with the metric k-cluster problem, the clique cover problem, and once again maximal independent sets. The clique cover problem asks us to find a partition of the vertex set of a graph into as few subsets Vi,..., Vk as possible such that, for each 1