0
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ 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. $\endgroup$
    – Chandra Chekuri
    Commented May 24, 2020 at 19:15
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yonatan N
    Commented May 24, 2020 at 23:54
  • $\begingroup$ Thanks for your useful information ! $\endgroup$
    – Laoxuexian
    Commented May 25, 2020 at 9:43

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.