# Dense subgraph

An example of a graph ${\displaystyle G}$ with density ${\displaystyle d_{G}=1.375}$ and its densest subgraph induced by the vertices ${\displaystyle b,c,d,e}$ and ${\displaystyle h}$ in red with density ${\displaystyle 1.4}$

In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let ${\displaystyle G=(E,V)}$ be an undirected graph and let ${\displaystyle S=(E_{S},V_{S})}$ be a subgraph of ${\displaystyle G}$. Then the density of ${\displaystyle S}$ is defined to be ${\displaystyle 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. One of them is the densest ${\displaystyle k}$ subgraph problem, where the objective is to find the maximum density subgraph on exactly ${\displaystyle k}$ vertices. This problem generalizes the clique problem and is thus NP-hard in general graphs. There exists a polynomial algorithm approximating the densest ${\displaystyle k}$ subgraph within a ratio of ${\displaystyle n^{1/4+\epsilon }}$ for every ${\displaystyle \epsilon >0}$,[1] while it does not admit an ${\displaystyle n^{1/{{\text{polyloglog }}n}}}$-approximation in polynomial time unless the exponential time hypothesis is false.[2] Under a weaker assumption that ${\displaystyle NP\subseteq \bigcap _{\epsilon >0}BPTIME(2^{n^{\epsilon }})}$, no PTAS exists for the problem.[3]

The problem remains NP-hard in bipartite graphs and chordal graphs but is polynomial for trees and split graphs.[4] 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.[5]

## Densest at most k subgraph

The objective of the densest at most ${\displaystyle k}$ problem is to find the maximum density subgraph on at most ${\displaystyle k}$ vertices. Anderson and Chellapilla showed that if there exists an ${\displaystyle \alpha }$ approximation for this problem then that will lead to an ${\displaystyle \Theta (\alpha ^{2})}$ approximation for the densest ${\displaystyle k}$ subgraph problem.

## Densest at least k subgraph

The densest at least ${\displaystyle k}$ problem is defined similarly to the densest at most ${\displaystyle k}$ subgraph problem. The problem is NP-complete,[6] but admits 2-approximation in polynomial time.[7] 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 ${\displaystyle (2-\epsilon )}$ factor for every constant ${\displaystyle \epsilon >0}$.[8]

## K-clique densest subgraph

Charalampos Tsourakakis introduced the ${\displaystyle k}$-clique densest subgraph problem. This variation of the densest subgraph problem aims to maximize the average number of induced ${\displaystyle k}$ cliques ${\displaystyle d_{k}(S)={|C_{k}(S)| \over |V_{S}|}}$, where ${\displaystyle C_{k}(S)}$ is the set of ${\displaystyle k}$-cliques induced by ${\displaystyle S}$. Notice that the densest subgraph problem is obtained as a special case for ${\displaystyle k=2}$. This generalization provides an empirically successful poly-time approach for extracting large near-cliques from large-scale real-world networks.

## References

1. ^ 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, MR 2743268.
2. ^ 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:, doi:10.1145/3055399.3055412.
3. ^ 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.
4. ^ 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.
5. ^ 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.
6. ^ 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, doi:10.1007/978-3-642-02927-1_50, MR 2544878
7. ^ Anderson, Reid (2007), Finding large and small dense subgraphs, arXiv:, Bibcode:2007cs........2032A
8. ^ Manurangsi, Pasin (2017), Inapproximability of Maximum Biclique Problems, Minimum k-Cut and Densest At-Least-k-Subgraph from the Small Set Expansion Hypothesis, arXiv:, Bibcode:2017arXiv170503581M