# Different version of approximation complexity and algorithm for densest-k-subgraph problem

In the densest-k-subgraph problem, we are given a graph $$G =(V,E)$$ and $$k$$, and we are asked to find a set $$S \in V$$ of vertices to maximize the number of edges in the induced graph of $$S$$, i.e. $$|Ind[S]|$$.

Let the optimal solution be $$S^*$$, the approximation problem finds another $$S$$ with size $$k$$ and the approximation ratio $$\alpha$$ means $$|Ind[S]| = \frac{1}{\alpha} |Ind[S^*]|$$. I have learned that there is an $$n^{1/4 +\epsilon}$$ approximation algorithm.

However，I want a different version of approximation: a $$\beta-$$approximation algorithm should return a vertices set $$S$$ of size $$\beta\cdot k$$ and $$|Ind[S]| \ge |Ind[S*]|$$.

I want to know if there are approximation algorithm for densest-k-subgraph under this definition of approximation, and some results on the hardness of approximation.

• The version you mention is also considered. It is known that a $\beta$-approximation for your problem implies a $\beta^2$-approximation for the original version via a simple argument. – Chandra Chekuri May 24 '20 at 19:15
• The phrase to search for is "Smallest m-Edge Subgraph" or similar. It has a $n^{3-2\sqrt{2}+\epsilon} \approx n^{.172+\epsilon}$ approximation, see arxiv.org/pdf/1205.0144.pdf . The statement of the result is in Corollary 6.2. The derivation uses basically the same log-density framework as does the $n^{1/4-\epsilon}$ algorithm for DkS, so an improvement in either result will likely imply something for the other. – Yonatan N May 24 '20 at 23:54