<p>This is me again, more than 3 years after asking this question.</p>

<p>Here is a code that can solve the weighted version of the problem in some real-world weighted graphs efficiently: <a href="https://github.com/maxdan94/HkS" rel="nofollow noreferrer">https://github.com/maxdan94/HkS</a></p>

<p>Please find a paper about the method here: <a href="https://zenodo.org/record/159769/files/main.pdf" rel="nofollow noreferrer">https://zenodo.org/record/159769/files/main.pdf</a></p>

<p>It uses branch&amp;bound.</p>

CC BY-SA 3.0
2017-02-10T14:23:22.260Z
(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.
Sasho Nikolov
CC BY-SA 3.0
2017-02-12T14:11:51.127Z
Thanks for your feedback. I have edited my answer. What do you mean by "I should accept an answer"?
maxdan94
CC BY-SA 3.0
2017-02-12T14:46:37.917Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-02-10T10:29:06.703Z
2017-02-12T14:12:43.653Z
2017-02-12T14:12:43.653Z
maxdan94
<p>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 <a href="https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability">wikipedia section on FPT and clique</a> for more.</p>

CC BY-SA 3.0
2013-12-19T22:36:18.300Z
2013-12-19T22:36:18.300Z
Austin Buchanan
<p>What is "the best" algorithm to find the densest subgraph of size k?</p>

<p>i.e. a subgraph of size k with the maximum number of edges inside for an unweighted and undirected graph.</p>

<p>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.</p>

CC BY-SA 3.0
2013-12-16T15:56:28.643Z
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](https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability).
Austin Buchanan
CC BY-SA 3.0
2013-12-19T21:11:59.947Z
@Austin, I think your comment can be an answer. :)
Kaveh
CC BY-SA 3.0
2013-12-20T01:00:48.953Z
You can easily remove a factor of k! by only selecting nodes in order.  Then your algorithm only takes O(n choose k)
dspyz
CC BY-SA 3.0
2013-12-20T01:03:02.733Z
Edit, we're both forgetting an extra factor of k^2 to count the number of edges in a particular selection
dspyz
<graph-theory><graph-algorithms>
find the densest subgraph of size k
maxdan94
# find the densest subgraph of size k

(Asked by: username_0 on 2013-12-16)

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.

**Tags:** graph-theory, graph-algorithms
> **Comments:**
> **username_1**: 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](https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability).  
> **username_2**: @Austin, I think your comment can be an answer. :)  
> **username_3**: You can easily remove a factor of k! by only selecting nodes in order.  Then your algorithm only takes O(n choose k)  
> **username_3**: Edit, we're both forgetting an extra factor of k^2 to count the number of edges in a particular selection  

---

## 2 answers

### Answer by username_1 on 2013-12-19. Score: 9 | Accepted answer

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](https://en.wikipedia.org/wiki/Clique_problem#Fixed-parameter_intractability) for more.


---

### Answer by username_0 on 2017-02-10. Score: -1

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.

> **Comments:**
> **username_4**: (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.  
> **username_0**: Thanks for your feedback. I have edited my answer. What do you mean by "I should accept an answer"?  
> **username_4**: 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.  

---

