## Abstract

In the Densest k-Subgraph problem, given a graph G and a parameter k, one needs to find a subgraph of G induced on k vertices that contains the largest number of edges. There is a significant gap between the best known upper and lower bounds for this problem. It is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms. On the other hand, the current best known algorithm of Feige, Kortsarz and Peleg, gives an approximation ratio of n ^{1/3 - ε} for some fixed ε>0 (later estimated at around ε= 1/90). We present an algorithm that for every ε> 0 approximates the Densest k-Subgraph problem within a ratio of n^{1/4+ε} in time n^{O(1/ε)}. If allowed to run for time n^{O(log n)}, the algorithm achieves an approximation ratio of O(n^{1/4}). Our algorithm is inspired by studying an average-case version of the problem where the goal is to distinguish random graphs from random graphs with planted dense subgraphs - the approximation ratio we achieve for the general case matches the "distinguishing ratio" we obtain for this planted problem. At a high level, our algorithms involve cleverly counting appropriately defined trees of constant size in G, and using these counts to identify the vertices of the dense subgraph. We say that a graph G(V,E) has log-density α if its average degree is Θ(|V|^{α}). The algorithmic core of our result is a procedure to output a k-subgraph of 'nontrivial' density whenever the log-density of the densest k-subgraph is larger than the log-density of the host graph. We outline an extension to our approximation algorithm which achieves an O(n^{1/4-ε})-approximation in O(2^{nO(ε)}) time. We also show that, for certain parameter ranges, eigenvalue and SDP based techniques can outperform our basic distinguishing algorithm for random instances (in polynomial time), though without improving upon the O(n ^{1/4}) guarantee overall.

Original language | English (US) |
---|---|

Title of host publication | STOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing |

Pages | 201-210 |

Number of pages | 10 |

DOIs | |

State | Published - Jul 23 2010 |

Event | 42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States Duration: Jun 5 2010 → Jun 8 2010 |

### Other

Other | 42nd ACM Symposium on Theory of Computing, STOC 2010 |
---|---|

Country | United States |

City | Cambridge, MA |

Period | 6/5/10 → 6/8/10 |

## Keywords

- approximation algorithm
- densest k subgraph
- lp hierarchies
- random planted model

## ASJC Scopus subject areas

- Software