A Note on Approximability of Densest At-Least-k-Subgraph
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916044593954816 |
|---|---|
| author | Laekhanukit, Bundit Manurangsi, Pasin Trabelsi, Ohad |
| author_facet | Laekhanukit, Bundit Manurangsi, Pasin Trabelsi, Ohad |
| contents | 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$). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_25464 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | A Note on Approximability of Densest At-Least-k-Subgraph Laekhanukit, Bundit Manurangsi, Pasin Trabelsi, Ohad Data Structures and Algorithms Computational Complexity 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$). |
| title | A Note on Approximability of Densest At-Least-k-Subgraph |
| topic | Data Structures and Algorithms Computational Complexity |
| url | https://arxiv.org/abs/2605.25464 |