Let G = (V, E) be an undirected graph with n nodes and m edges. For a subset , we use G[X]...

Let G = (V, E) be an undirected graph with n nodes and m edges. For a subset , we use G[X] to denote the subgraph induced on X–that is, the graph whose node set is X and whose edge set consists of all edges of G for which both ends lie in X.

We are given a natural number k ≤ n and are interested in finding a set of k nodes that induces a "dense" subgraph of G; we ll phrase this concretely as follows. Give a polynomial-time algorithm that produces, for a given natural number k ≤ n, a set  of k nodes with the property that the induced subgraph G[X] has at least  edges.

You may give either (a) a deterministic algorithm, or (b) a randomized algorithm that has an expected running time that is polynomial, and that only outputs correct answers.