Finding the subgraph with maximum average degree. Complexity?

Question

Is there an efficient algorithm to find the subgraph with the largest average degree (which may be the graph itself)?

Answer 1

The paper "Finding a Maximum-Density Subgraph" by Andrew Goldberg gives a polynomial-time algorithm for identifying such a graph. It looks like the algorithm makes logarithmically many calls to a max-flow algorithm on appropriately constructed graphs. From what I've read, it looks like the algorithm is just a binary search over the average degree where each guess is checked using a maximum flow on a standard graph construction. Most of the complexity appears to be in arguing why the construction is correct.

Hope this helps!