Let G = (V, E) be an undirected graph with n nodes and m edges. For a subset X ⊆ V, 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 X ⊆ V 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.