Constant-gap NP-hardness of densest k-subgraph
Let $G = (V, E)$ be a finite simple undirected graph, given explicitly, with $n = |V|$. For an integer $2 \le k \le n$ let $$\operatorname{OPT}_k(G) = \max_{S \subseteq V,\ |S| = k} |E(G[S])|,$$ the largest number of edges of an induced subgraph on $k$ vertices. The input also includes an integer $1 \le \ell \le \binom{k}{2}$. Computing $\operatorname{OPT}_k$ exactly is NP-hard, by reduction from Clique. Feige, Kortsarz and Peleg gave a polynomial-time approximation within a factor $O(n^\delta)$ for some $\delta < 1/3$, and Bhaskara, Charikar, Chlamtac, Feige and Vijayaraghavan one within $O(n^{1/4 + \varepsilon})$ in time $n^{O(1/\varepsilon)}$. Khot proved that there is no polynomial-time approximation scheme unless $\mathrm{NP} \subseteq \bigcap_{\varepsilon > 0} \mathrm{BPTIME}(2^{n^\varepsilon})$, and Manurangsi that, under the Exponential Time Hypothesis, no polynomial-time algorithm approximates within $n^{1/(\log\log n)^c}$ for a universal constant $c > 0$.
Problem. Is there an absolute rational constant $\lambda > 1$ for which it is NP-hard to distinguish $$\operatorname{OPT}_k(G) \ge \ell \qquad \text{from} \qquad \operatorname{OPT}_k(G) < \frac{\ell}{\lambda}\,?$$ NP-hardness here means a deterministic polynomial-time many-one reduction: one map, with output size polynomial in the input length, takes every Boolean formula in 3-conjunctive normal form to an instance $(G, k, \ell)$, sending satisfiable formulas to the first case and unsatisfiable ones to the second. The factor $\lambda$ is fixed independently of the input, while $k$ may grow with it; instances between the two thresholds need no prescribed answer. No hardness assumption beyond the reduction itself is allowed.
Source: Feige, Kortsarz and Peleg (2001), §1, who conjecture that approximating within a factor 1 + ε is NP-hard; in this gap form, Laekhanukit, Manurangsi and Trabelsi (2026), §1 and Definition 1. Stated by AIM — Open Applied Problems.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- OC
- Keywords
- AIM Open Applied Problems, densest k-subgraph, hardness of approximation
References
@article{feige2001,
author = {Feige, Uriel and Kortsarz, Guy and Peleg, David},
title = {The dense {$k$}-subgraph problem},
journal = {Algorithmica},
volume = {29},
number = {3},
year = {2001},
pages = {410--421},
doi = {10.1007/s004530010050},
}
@misc{laekhanukit2026,
author = {Laekhanukit, Bundit and Manurangsi, Pasin and Trabelsi, Ohad},
title = {A note on approximability of densest at-least-{$k$}-subgraph},
year = {2026},
eprint = {2605.25464},
archivePrefix = {arXiv},
}
@inproceedings{bhaskara2010,
author = {Bhaskara, Aditya and Charikar, Moses and Chlamtac, Eden and Feige, Uriel and Vijayaraghavan, Aravindan},
title = {Detecting high log-densities: an {$O(n^{1/4})$} approximation for densest {$k$}-subgraph},
booktitle = {Proceedings of the 42nd ACM Symposium on Theory of Computing},
publisher = {ACM},
year = {2010},
pages = {201--210},
doi = {10.1145/1806689.1806719},
}
@article{khot2006,
author = {Khot, Subhash},
title = {Ruling out {PTAS} for graph min-bisection, dense {$k$}-subgraph, and bipartite clique},
journal = {SIAM J. Comput.},
volume = {36},
number = {4},
year = {2006},
pages = {1025--1071},
doi = {10.1137/S0097539705447037},
}
@inproceedings{manurangsi2017,
author = {Manurangsi, Pasin},
title = {Almost-polynomial ratio {ETH}-hardness of approximating densest {$k$}-subgraph},
booktitle = {Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing},
publisher = {ACM},
year = {2017},
pages = {954--961},
doi = {10.1145/3055399.3055412},
eprint = {1611.05991},
archivePrefix = {arXiv},
}
@misc{aim-densest-k-subgraph-constant-gap-hardness,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Constant-gap NP-hardness of densest k-subgraph}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/492-densest-k-subgraph-constant-gap-hardness.md},
note = {Entry 492 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00423, "Constant-gap NP-hardness of densest k-subgraph", clopen.solutions.