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

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

<p>However，I want a different version of approximation: a <span class="math-container">$\beta-$</span>approximation algorithm should return a vertices set <span class="math-container">$S$</span> of size <span class="math-container">$\beta\cdot k$</span> and <span class="math-container">$|Ind[S]| \ge |Ind[S*]|$</span>. </p>

<p>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.</p>

<p>Thanks in advance.</p>

CC BY-SA 4.0
2020-05-24T19:15:34.293Z
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
CC BY-SA 4.0
2020-05-24T23:54:30.370Z
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 https://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
CC BY-SA 4.0
2020-05-25T09:43:20.000Z
Thanks for your useful information !
Laoxuexian
<graph-theory><approximation-algorithms><approximation-hardness>
Different version of approximation complexity and algorithm for densest-k-subgraph problem
Laoxuexian
# Different version of approximation complexity and algorithm for densest-k-subgraph problem

(Asked by: username_0 on 2020-05-24)

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.

Thanks in advance.

**Tags:** graph-theory, approximation-algorithms, approximation-hardness
> **Comments:**
> **username_1**: 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.  
> **username_2**: 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 https://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.  
> **username_0**: Thanks for your useful information !  

---

## 0 answers

