A Note on Approximability of Densest At-Least-k-Subgraph
2026-05-25 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational Complexity
AI summaryⓘ
The authors study a problem where you want to find a dense subgraph with at least k nodes in a given graph. They show that if finding the densest subgraph with exactly k nodes is hard to approximate well, then finding the densest subgraph with at least k nodes is also hard to approximate within certain factors. They improve previous results by giving stronger evidence of this hardness under less restrictive assumptions and prove the problem is also hard in a parameterized sense. Additionally, they show that finding the exact solution is computationally difficult when parameterized by k.
Densest At-Least-k-SubgraphDensest k-Subgraphapproximation algorithmshardness of approximationparameterized complexityW[1]-hardnessSmall Set Expansion Hypothesisgraph densitypolynomial time algorithms
Authors
Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi
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, independently discovered by Khuller and Saha (2009) and by Andersen (2007), yields 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 in both the normal (non-parameterized) and the parameterized (by $k$) settings. We then generalize 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 - δ}$ factor for any constant $δ> 0$. Once again, this extends naturally to the parameterized setting. Previously, $(2 - \varepsilon)$ factor inapproximability for DAL$k$S was 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$).