A Note on Approximability of Densest At-Least-k-Subgraph
Abstract
We study the Densest At-Least-$k$-Subgraph (DAL$k$S) problem, in which we are given an undirected graph $G$ and an integer $k$, and the goal is to find a subgraph of $G$ with at least $k$ vertices with maximum density. The best known algorithm due independently to Khuller and Saha (2009) and Andersen (2007) gives a 2-approximation for DAL$k$S in polynomial time.
In this note, we provide a (simple) reduction from Densest $k$-Subgraph (D$k$S) to Densest At-Least-$k$-Subgraph, which shows that, if D$k$S is hard to approximate to within any constant factor, then DAL$k$S is hard to approximate to within $(3/2 - \varepsilon)$ factor for every $\varepsilon > 0$. This holds both in the normal (non-parameterized) and parameterized (by $k$) settings.
We then generalizes the reduction to provide a tight $(2 - \varepsilon)$ factor hardness of approximating Densest At-Least-$k$-Subgraph, albeit under a stronger hypothesis which roughly states that Densest $k$-Subgraph is hard to approximate to within $k^{1 - \delta}$ factor for any constant $\delta > 0$. Once again, this extends naturally to the parameterized setting. Previously, $(2 - \varepsilon)$ factor inapproximability for DAL$k$S is only known under the Small Set Expansion Hypothesis (Bergner 2013; Manurangsi 2017), which does not apply to the parameterized version of the problem.
Furthermore, we show that the exact version of DAL$k$S is $W[1]$-hard (parameterized by $k$).
In this note, we provide a (simple) reduction from Densest $k$-Subgraph (D$k$S) to Densest At-Least-$k$-Subgraph, which shows that, if D$k$S is hard to approximate to within any constant factor, then DAL$k$S is hard to approximate to within $(3/2 - \varepsilon)$ factor for every $\varepsilon > 0$. This holds both in the normal (non-parameterized) and parameterized (by $k$) settings.
We then generalizes the reduction to provide a tight $(2 - \varepsilon)$ factor hardness of approximating Densest At-Least-$k$-Subgraph, albeit under a stronger hypothesis which roughly states that Densest $k$-Subgraph is hard to approximate to within $k^{1 - \delta}$ factor for any constant $\delta > 0$. Once again, this extends naturally to the parameterized setting. Previously, $(2 - \varepsilon)$ factor inapproximability for DAL$k$S is only known under the Small Set Expansion Hypothesis (Bergner 2013; Manurangsi 2017), which does not apply to the parameterized version of the problem.
Furthermore, we show that the exact version of DAL$k$S is $W[1]$-hard (parameterized by $k$).
