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 [10], 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. 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 n O(ε) ) 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.
The current best-known approximation for DkS is O(n 1/4+ ) for arbitrarily small constant > 0, due to Bhaskara et al. REF .
Detecting high log-densities: an O(n¼) approximation for densest k-subgraph
STOC '10
Mathematics Computer Science