New Approximation Algorithms for Densest k-Subgraph

by Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige and Aravindan Vijayaraghavan.

Oded's comments

I was and am intrigued by the fact that the design of the algorithm (for the worst-case problem) was actually guided by the analysis of the planted randomn instance model. This seems related to the fact that a key aspect of the problem at hand can be related to structures that are in some sense random (or better than random, where deviations from random are employed to the benefit of the algorithm).

The original abstract

We consider the Densest $k$-Subgraph (DkS) problem: Given a graph $G$ and a parameter $k$, find a subgraph of $G$ on $k$ vertices with the maximum number of edges. This is a well known optimization problem, which is a natural optimization version of the decision problem k-CLIQUE. The previous best known approximation ratio by Feige, Kortsarz and Peleg in 2001 was $O(n^{1/3-\epsilon})$ for $\epsilon$ estimated at around 1/60. We improve on this result, giving an $O(n^{1/4+\epsilon})$ approximation for any $\epsilon>0$. In essence, our algorithm relies on the following principle: In a random graph with average degree $n^{\alpha}$, a planted $k$-subgraph can be detected if it has average degree (strictly) greater than $k^{\alpha}$. We show that this principle largely carries over to provide results in the same spirit for worst-case (non-random) instances.


Back to list of Oded's choices.