Dense subgraph

An example of a graph G with density d_G = 1.375 and it's densest subgraph induced by the vertices b,c,d and h in red with density 1.4

In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let G = (E,V) be an undirected graph and let S = (E_S,V_S) be a subgraph of G. Then the density of S is defined to be $d_S = {|E_S|\over|V_S|}$.

The densest subgraph problem is that of finding a subgraph of maximum density. In 1984, A. V. Goldberg developed a polynomial time algorithm to find the maximum density subgraph using a max flow technique.

Densest k subgraph

There are many variations on the densest subgraph problem. There is the densest k subgraph problem, where the objective is to find the maximum density subgraph on exactly k vertices. This problem is known to be NP-Hard by a reduction from the clique problem. The densest k subgraph problem is NP-Complete even in planar graphs by a reduction from the connected vertex cover problem on planar graphs with maximum degree 4. There does not exist a polynomial-time approximation scheme (PTAS) for the densest k subgraph problem this is by a reduction from the Minimum Distance of Code problem.

Densest at most k subgraph

The objective of the densest at most k problem is to find the maximum density subgraph on at most k vertices. Anderson and Chellapilla showed that if there exists an α approximation for this problem then that will lead to an Θ(α²) approximation for the densest k subgraph problem.

Densest at least k subgraph

The densest at least k problem is defined similarly to the densest at most k subgraph problem. There is a 2-approximation due to Anderson. But the complexity of this problem is still unknown.

References

• Goldberg, A. V. (1984), "Finding a maximum density subgraph", Technical report .
• Feige, U.; Kortsarz, G.; Peleg, D. (1997), "The dense k-subgraph problem", Algorithmica 29: 410–421 .
• Keil, J.; Brecht, T. (1991), "The complexity of clustering in planar graphs", The Journal of Combinatorial Mathematics and Combinatorial Computing 9: 155–159 .
• Khot, S. (2006), "Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique", SIAM Journal of Computing 36: 1025–1071 .
• Anderson, R.; Chellapilla, K. (2009), "Finding dense subgraphs with size bounds", WAW: 25–36 .
• Anderson, R. (2007), "Finding large and small dense subgraphs", CoRR .
• Khuller, S.; Saha, B. (2009), "On finding dense subgraphs", The International Colloquium on Automata, Languages and Programming .