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.

Improve this question
$\endgroup$
4
  • 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, 2013 at 15:56
  • $\begingroup$ @Austin, I think your comment can be an answer. :) $\endgroup$
    – Kaveh
    Dec 19, 2013 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, 2013 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, 2013 at 1:03

2 Answers 2

Reset to default
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.

Improve this answer
$\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.

Improve this answer
$\endgroup$
3
  • $\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, 2017 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, 2017 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, 2017 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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