Dense subgraph

From Wikipedia, the free encyclopedia
An example of a graph G with density d_{G}=1.375 and it's densest subgraph induced by the vertices b,c,d,e 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, Andrew 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 \alpha approximation for this problem then that will lead to an \Theta (\alpha ^{2}) 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 on 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 .
This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.