# 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 wikipedia section on FPT and clique. Dec 16, 2013 at 15:56
• @Austin, I think your comment can be an answer. :) Dec 19, 2013 at 21:11
• You can easily remove a factor of k! by only selecting nodes in order. Then your algorithm only takes O(n choose k) Dec 20, 2013 at 1:00
• Edit, we're both forgetting an extra factor of k^2 to count the number of edges in a particular selection Dec 20, 2013 at 1:03

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.

This is me again, more than 3 years after asking this question.

Here is a code that can solve the weighted version of the problem in some real-world weighted graphs efficiently: https://github.com/maxdan94/HkS