Planted Models for the Densest $k$ Subgraph Problem
Given an undirected graph $G$ the Densest $k$ subgraph problem (DkS) asks to compute a set $S \subset V$ of cardinality \left\lvert S\right\rvert \leq k$ such that the weight of edges inside $S$ is maximized. This is a fundamental NP hard problem whose approximability, inspite of many decades of research, is yet to be settled. The current best known approximation algorithm due to Bhaskara et al. (2010) computes a \mathcal{O}\left({n^{1/4 \epsilon}\right) approximation in time $n^\mathcal{O}\left(1/\epsilon\right) We ask what are some "easier" instances of this problem? We propose some natural semi random models of instances with a planted dense subgraph, and study approximation algorithms for computing the densest subgraph in them. These models are inspired by the semi random models of instances studied for various other graph problems such as the independent set problem, graph partitioning problems etc. For a large range of parameters of these models, we get significantly better approximation factors for the Densest $k$ subgraph problem. Moreover, our algorithm recovers a large part of the planted solution.
FSTTCS