3
$\begingroup$

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.

$\endgroup$
  • 10
    $\begingroup$ 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. $\endgroup$ – Austin Buchanan Dec 16 '13 at 15:56
  • $\begingroup$ @Austin, I think your comment can be an answer. :) $\endgroup$ – Kaveh Dec 19 '13 at 21:11
  • $\begingroup$ You can easily remove a factor of k! by only selecting nodes in order. Then your algorithm only takes O(n choose k) $\endgroup$ – dspyz Dec 20 '13 at 1:00
  • $\begingroup$ Edit, we're both forgetting an extra factor of k^2 to count the number of edges in a particular selection $\endgroup$ – dspyz Dec 20 '13 at 1:03
9
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

Please find a paper about the method here: https://zenodo.org/record/159769/files/main.pdf

It uses branch&bound.

$\endgroup$
  • $\begingroup$ (1) you should accept an answer. (2) what is a "real-world weighted graph"? Graphs can arise in all kinds of contexts in the real world, and can have very different properties. If you are going to declare an algorithm with no proven guarantees efficient for "real-world [...] graphs" then you should give some information about what it has been tested on and how, possibly link to a paper. $\endgroup$ – Sasho Nikolov Feb 10 '17 at 14:23
  • $\begingroup$ Thanks for your feedback. I have edited my answer. What do you mean by "I should accept an answer"? $\endgroup$ – maxdan94 Feb 12 '17 at 14:11
  • $\begingroup$ It means to mark one of the two answers as "accepted" by clicking on the grey tickmark next to it, so that the question does not keep popping up as unanswered. $\endgroup$ – Sasho Nikolov Feb 12 '17 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.