find the densest subgraph of size k 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.
An answer to your problem tells you whether there exists a clique of size k. So, any such algorithm for your problem must be at least as slow as clique algorithms. See the wikipedia section on FPT and clique for more.