## New Approximation Algorithms for Densest k-Subgraph

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

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.