CODEWITHSUNDEEP
algorithmgraph-theorygraph-algorithm
user9278
user9278

Reputation: 86

Finding the subgraph with maximum average degree. Complexity?

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

Upvotes: 6

Views: 1099

Answers (1)

templatetypedef
templatetypedef

Reputation: 373482

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!

Upvotes: 5

Related Questions