NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph
Let OPT(G,k)=max_{S subseteq V(G), |S|=k}|E(G[S])| for a finite simple undirected input graph G. Prove or refute the assertion that there exists an absolute constant epsilon>0 for which the promise problem of distinguishing OPT(G,k)>=t from OPT(G,k)<t/(1+epsilon), with input integers 1<=k<=|V(G)| and t>=1, is NP-hard under deterministic polynomial-time gap reductions. The target is any fixed nontrivial constant approximation gap for exactly k vertices, based on NP-hardness rather than a stronger average-case or exponential-time assumption.
Status Open Status review date not recorded in this edition
Listed by ProofAtlas. Status qualification is attributed to ProofAtlas; no full resolution is certified here.
References
Primary source
ProofAtlas open problems; Bundit Laekhanukit, Pasin Manurangsi and Ohad Trabelsi, A Note on Approximability of Densest At-Least-k-Subgraph, arXiv:2605.25464v1 (25 May 2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.