Detecting high log-densities - An O(n1/4) approximation for densest k-subgraph

Aditya Bhaskara*, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

181 Scopus citations

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 n1/4+ε in time nO(1/ε). If allowed to run for time nO(log n), the algorithm achieves an approximation ratio of O(n1/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(n1/4-ε)-approximation in O(2nO(ε)) 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 languageEnglish (US)
Title of host publicationSTOC'10 - Proceedings of the 2010 ACM International Symposium on Theory of Computing
Pages201-210
Number of pages10
DOIs
StatePublished - Jul 23 2010
Event42nd ACM Symposium on Theory of Computing, STOC 2010 - Cambridge, MA, United States
Duration: Jun 5 2010Jun 8 2010

Other

Other42nd ACM Symposium on Theory of Computing, STOC 2010
CountryUnited States
CityCambridge, MA
Period6/5/106/8/10

Keywords

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

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Detecting high log-densities - An O(n<sup>1/4</sup>) approximation for densest k-subgraph'. Together they form a unique fingerprint.

Cite this