Dense subgraph

An example of a graph $G$ with density $d_{G}=1.375$ and its 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. One of them is the densest $k$ subgraph problem, where the objective is to find the maximum density subgraph on exactly $k$ vertices. This problem generalizes the clique problem and is thus NP-hard in general graphs. There exists a polynomial algorithm approximating the densest $k$ subgraph within a ratio of $n^{1/4+\epsilon }$ for every $\epsilon >0$,^[1] while it does not admit PTAS unless $NP\subseteq \bigcap _{\epsilon >0}BPTIME(2^{n^{\epsilon }})$.^[2] The problem remains NP-hard in bipartite graphs and chordal graphs but is polynomial for trees and split graphs.^[3] 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.^[4]

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. It is also NP-complete.^[5]

K-clique densest subgraph

Charalampos Tsourakakis introduced the $k$-clique densest subgraph problem. This variation of the densest subgraph problem aims to maximize the average number of induced $k$ cliques $d_{k}(S)={|C_{k}(S)| \over |V_{S}|}$, where $C_{k}(S)$ is the set of $k$-cliques induced by $S$. Notice that the densest subgraph problem is obtained as a special case for $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(n^1/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. Khot, Subhash (2006), "Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique", SIAM Journal on Computing 36 (4): 1025–1071, doi:10.1137/S0097539705447037, MR 2272270, CiteSeerX: 10.1.1.114.3324.
3. 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 754426.
4. 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.
5. 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

Additional reading

• Anderson, R.; Chellapilla, K. (2009), "Finding dense subgraphs with size bounds", WAW: 25–36.
• Anderson, R. (2007), Finding large and small dense subgraphs, arXiv:cs/0702032.
• Feige, U.; Kortsarz, G.; Peleg, D. (1997), "The dense k-subgraph problem", Algorithmica 29: 410–421, doi:10.1007/s004530010050.
• Goldberg, A. V. (1984), "Finding a maximum density subgraph", Technical report.
• Tsourakakis, C. (2015), "The k-clique densest subgraph problem", The International World Wide Web Conference, doi:10.1145/2736277.2741098.