What is "the best" algorithm to find the densest subgraph of size k?
i.e. a subgraph of size k with the maximum number of edges inside for an unweighted and undirected graph.
For fixed k, the straightforward brute-force algorithm takes $O(n^k)$ time with n the number of nodes. I'm looking for something, like $O(2^kn)$ or so. Maybe using a recursive algorithm or dynamic programming.