Dense subgraph

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
An example of a graph with density and its densest subgraph induced by the vertices and in red with density

In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let be an undirected graph and let be a subgraph of . Then the density of is defined to be .

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. This has been improved by Gallo, Grigoriadis and Tarjan in 1989[1] to run in time. A simple LP for finding the optimal solution was given by Charikar in 2000.[2]

Densest k subgraph[edit]

There are many variations on the densest subgraph problem. One of them is the densest subgraph problem, where the objective is to find the maximum density subgraph on exactly vertices. This problem generalizes the clique problem and is thus NP-hard in general graphs. There exists a polynomial algorithm approximating the densest subgraph within a ratio of for every ,[3] while it does not admit an -approximation in polynomial time unless the exponential time hypothesis is false.[4] Under a weaker assumption that , no PTAS exists for the problem.[5]

The problem remains NP-hard in bipartite graphs and chordal graphs but is polynomial for trees and split graphs.[6] It is open whether the problem is NP-hard or polynomial in (proper) interval graphs and planar graphs; however, a variation of the problem in which the subgraph is required to be connected is NP-hard in planar graphs.[7]

Densest at most k subgraph[edit]

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

Densest at least k subgraph[edit]

The densest at least problem is defined similarly to the densest at most subgraph problem. The problem is NP-complete,[8] but admits 2-approximation in polynomial time.[9] Moreover, there is some evidence that this approximation algorithm is essentially the best possible: assuming the Small Set Expansion Hypothesis (a computational complexity assumption closely related to the Unique Games Conjecture), then it is NP-hard to approximate the problem to within factor for every constant .[10]

K-clique densest subgraph[edit]

Charalampos Tsourakakis introduced the -clique densest subgraph problem. This variation of the densest subgraph problem aims to maximize the average number of induced cliques , where is the set of -cliques induced by . Notice that the densest subgraph problem is obtained as a special case for . This generalization provides an empirically successful poly-time approach for extracting large near-cliques from large-scale real-world networks.

Locally top-k densest subgraph[edit]

Qin et al. introduced the problem of top-k locally densest subgraphs discovery in a graph, each of which achieves the highest density in its local region in the graph: it is neither contained in any supergraph with the same or larger density, nor it contains subgraphs with density being loosely connected with the rest of the local densest subgraph. Note that the densest subgraph problem is obtained as a special case for . The set of locally densest subgraphs in a graph can be computed in polynomial time.


  1. ^ Gallo, Giorgio; Grigoriadis, Michael D.; Tarjan, Robert E. (1989). "A Fast Parametric Maximum Flow Algorithm and Applications". SIAM Journal on Computing. 18 (1): 30–55. doi:10.1137/0218003.
  2. ^ Charikar (2000). "Greedy approximation algorithms for finding dense components in a graph". In Klaus Jansen; Samir Khuller (eds.). APPROX '00: Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization. Berlin, Heidelberg: Springer-Verlag. ISBN 978-3-540-67996-7.
  3. ^ Bhaskara, Aditya; Charikar, Moses; Chlamtáč, Eden; Feige, Uriel; Vijayaraghavan, Aravindan (2010), "Detecting high log-densities—an O(n1/4) approximation for densest k-subgraph", STOC'10—Proceedings of the 2010 ACM International Symposium on Theory of Computing, ACM, New York, pp. 201–210, doi:10.1145/1806689.1806719, ISBN 9781450300506, MR 2743268.
  4. ^ Manurangsi, Pasin (2017), "Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph", STOC'17—Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, ACM, pp. 954–961, arXiv:1611.05991, doi:10.1145/3055399.3055412, ISBN 9781450345286.
  5. ^ Khot, Subhash (2006), "Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique", SIAM Journal on Computing, 36 (4): 1025–1071, CiteSeerX, doi:10.1137/S0097539705447037, MR 2272270.
  6. ^ Corneil, D. G.; Perl, Y. (1984), "Clustering and domination in perfect graphs", Discrete Applied Mathematics, 9 (1): 27–39, doi:10.1016/0166-218X(84)90088-X, MR 0754426.
  7. ^ Keil, J. Mark; Brecht, Timothy B. (1991), "The complexity of clustering in planar graphs" (PDF), Journal of Combinatorial Mathematics and Combinatorial Computing, 9: 155–159, MR 1111849.
  8. ^ Khuller, Samir; Saha, Barna (2009), "On finding dense subgraphs" (PDF), Automata, Languages and Programming: 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, Lecture Notes in Computer Science, 5555, Berlin: Springer-Verlag, pp. 597–608, CiteSeerX, doi:10.1007/978-3-642-02927-1_50, ISBN 978-3-642-02926-4, MR 2544878
  9. ^ Anderson, Reid (2007), Finding large and small dense subgraphs, arXiv:cs/0702032, Bibcode:2007cs........2032A
  10. ^ Manurangsi, Pasin (2017), Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis, arXiv:1705.03581, Bibcode:2017arXiv170503581M

Further reading[edit]