NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph

NP-Hardness of Constant-Factor Approximation for Densest k-Subgraph

Definitions and mathematical statement

For a finite simple graph $G$ and $1\le k\le|V(G)|$, define \[ \operatorname{OPT}(G,k)=\max_{\substack{S\subseteq V(G)\\|S|=k}}|E(G[S])|. \] The assertion seeks an absolute ${\varepsilon}>0$ such that distinguishing \[ \operatorname{OPT}(G,k)\ge t \quad\text{from}\quad \operatorname{OPT}(G,k)<\frac{t}{1+{\varepsilon}} \] is NP-hard under deterministic polynomial-time gap reductions, for positive integer threshold $t$. A gap reduction maps yes-instances of an NP-hard language to the first promise and no-instances to the second. Inputs inside the gap need not be classified. The selected subgraph has exactly $k$ vertices; an at-least-$k$ density problem is not interchangeable. Hardness conditional on an average-case conjecture or a stronger time hypothesis does not establish the stated NP-hardness.

Formulation and concept references: [S1].

Short English statement

Is approximating the maximum number of edges induced by exactly $k$ vertices within some fixed nontrivial constant factor already NP-hard?

Research attempt

Status: UNRESOLVED. This attempt does not construct the deterministic polynomial-time constant-gap reduction requested above. It proves several elementary approximation and parameter reductions, measures the loss in the obvious reduction from CLIQUE, and identifies why neither a simple blow-up nor a natural linear relaxation closes that loss. The finite checks concern these intermediate statements, not NP-hardness.

Source and quantifier audit.

The source [S1], consulted on 27 September 2026, transfers suitable hardness assumptions about Densest $k$-Subgraph to an at-least-$k$ problem. Its use of constant-factor Densest $k$-Subgraph hardness as a premise must not be read as a proof of that premise. I retain the exact deterministic gap formulation in the definition. The graph size, $k$, and the threshold may all grow along a reduction. Showing hardness for exact optimization, or ruling out an algorithm only under a stronger time or average-case hypothesis, would leave the stated task unfinished.

Write $n=|V(G)|$, $m=|E(G)|$, and $M_k=\operatorname{OPT}(G,k)$. The interesting range has $2\le k<n$ and $1\le t\le\binom{k}{2}$. For $k=1$ the optimum is zero; for $k=n$ it is simply $m$. A multiplicative guarantee needs no special interpretation when $M_k=0$: every $k$-set is then optimal. These elementary boundary cases should be removed before trying to amplify a gap.

1. What the CLIQUE reduction actually supplies.

For $k\ge3$, use the same graph and let $t=\binom{k}{2}$. The case $k=2$ merely asks whether an edge exists and is decided directly. A $k$-clique gives $M_k=t$, whereas its absence gives $M_k\le t-1$. To force the latter into the strict no-promise of the problem using this information alone, one would need \[ t-1<\frac{t}{1+\varepsilon},\qquad \varepsilon<\frac{1}{t-1}. \] For growing $k$, this is a vanishing gap. The issue is not merely an imprecise bound: the graph on exactly $k$ vertices consisting of $K_k$ with one edge removed has $M_k=t-1$. Thus the elementary reduction encounters instances with the exact worst-case deficit of one edge.

A useful diagnostic is to replace each vertex by $b$ independent twins and each old edge by a complete bipartite graph between the corresponding twin sets. For the two graphs just considered, take the new target to be $bk$, so all vertices must be selected. Their optima are exactly $b^2t$ and $b^2(t-1)$. The ratio remains $t/(t-1)$. This calculation is deliberately restricted to these instances; for arbitrary graphs and other target sizes, a blow-up can redistribute the selected vertices between clusters, and asserting that the optimum automatically scales by $b^2$ would require a separate argument.

Even an idealized product operation would have a size problem. Suppose, only for this calculation, that an $r$-fold construction raised the yes/no ratio to $(t/(t-1))^r$ and used $n^r$ vertices. A fixed gap $1+\varepsilon$ requires \[ r\ge\frac{\log(1+\varepsilon)}{\log(t/(t-1))} =\Theta_{\varepsilon}(t). \] Then $n^r$ is not bounded by a polynomial of fixed degree when $k$ grows. This is not a theorem that all amplification fails. It locates the precise inadequacy of a naive tensor-power argument, even granting an optimum identity which a real construction would still have to prove.

2. A complete elementary approximation bound.

A uniformly random $k$-subset contains each edge with probability \[ \frac{k(k-1)}{n(n-1)}. \] Linearity of expectation gives a set with at least \[ m\frac{k(k-1)}{n(n-1)} \ge M_k\frac{k(k-1)}{n(n-1)} \] edges. This proves an $n(n-1)/(k(k-1))$ approximation. In particular, for $k$ a fixed positive fraction of $n$, it is a constant-factor approximation. It is not a $1+\varepsilon$ approximation, and it provides no contradiction to the proposed hardness for unrestricted $k$.

The existence proof can be made deterministic without solving Densest $k$-Subgraph. Let $A$ be the vertices already selected, $B$ the undecided vertices, $b=|B|$, and $r=k-|A|$. If the last $r$ vertices are chosen uniformly from $B$, the expected final edge count is \[ F(A,B,r)=e(A)+\frac{r}{b}e(A,B) +\frac{r(r-1)}{b(b-1)}e(B). \] Here $e(A,B)$ counts edges between the two disjoint sets. Interpret the last term as zero when $b\le1$, and handle $r=0$ or $r=b$ by making the forced choices. If $0<r<b$, expose a vertex $v\in B$. The current expectation is the weighted average, with weights $r/b$ and $1-r/b$, of the expectations obtained by including or excluding $v$. At least one branch does not decrease $F$. Choose it and continue. After at most $n$ decisions the conditional expectation is the actual integer edge count of a $k$-set. All counts and comparisons use rational numbers of polynomial bit length. This proves a deterministic polynomial-time version of the bound.

The argument supplies a concrete algorithm on dense parameter ranges, but it also quantifies its limitation: when $k/n$ tends to zero, the guaranteed fraction of the optimum can tend to zero. Replacing $m$ by the unknown number of edges in an optimum set inside this algorithm would be circular.

3. Exact, at-most, and at-least cardinality.

Padding a selected set by additional vertices cannot remove induced edges. Consequently, for this unweighted total-edge objective, \[ \max_{|S|\le k}e(S)=M_k. \] That identity is sometimes useful, but it says nothing similar about maximizing $e(S)/|S|$ over $|S|\ge k$. For example, in $K_n$ the latter maximum is $(n-1)/2$, attained by all $n$ vertices, whereas the density of any exact $k$-set is $(k-1)/2$. Their ratio can be arbitrarily large.

There are two distinct monotonicities for exact cardinalities. Padding proves $M_{k+1}\ge M_k$. Conversely, delete a uniformly chosen vertex from a maximizing $(k+1)$-set. Each of its edges survives with probability $(k-1)/(k+1)$, so \[ M_k\ge\frac{k-1}{k+1}M_{k+1},\qquad \frac{M_k}{\binom{k}{2}} \ge\frac{M_{k+1}}{\binom{k+1}{2}} \quad(k\ge2). \] Thus total optimum edge count increases with $k$, while normalized optimum edge density decreases. Neither statement identifies a single vertex ordering whose every prefix is optimal. An argument that repeatedly deletes the least useful vertex would need an approximation analysis, rather than an appeal to either monotonicity alone.

4. A relaxation with a calculable integrality gap.

Consider variables $0\le x_v\le1$, $\sum_vx_v=k$, and, for edges, $0\le y_{uv}\le x_u,x_v$, with objective $\sum_{uv\in E}y_{uv}$. Integral feasible points encode $k$-sets, but the relaxation is weak. On $K_n$, assigning every $x_v=y_{uv}=k/n$ gives objective $k(n-1)/2$. This is optimal for the relaxation, because \[ \sum_{uv}y_{uv}\le\frac12\sum_{uv}(x_u+x_v) =\frac{n-1}{2}\sum_vx_v=\frac{k(n-1)}2. \] The integral optimum is $k(k-1)/2$, so the ratio is exactly $(n-1)/(k-1)$ for $k\ge2$. This becomes unbounded for fixed $k$ and growing $n$, even though complete graphs are trivially solvable.

This example separates a relaxation obstruction from computational hardness. It proves that a guarantee derived only by comparing a rounded solution with this LP's objective cannot have a bounded integrality-gap analysis. It does not prove that no algorithm can recognize and handle the same instances. Additional constraints, different relaxations, or combinatorial algorithms remain possible. Conversely, merely exhibiting a stronger relaxation would not establish the requested NP-hardness.

5. Two tractable parameter regimes that a reduction must avoid.

For each fixed $k$, exhaustive enumeration of all $\binom nk$ subsets is polynomial in $n$, although its exponent depends on $k$. There is also an elementary fixed-threshold algorithm. To decide whether $M_k\ge t$ for a fixed positive integer $t$, enumerate every set of $t$ edges. If their incident vertices number at most $k$, pad that support to a $k$-set. It contains the chosen $t$ edges. Conversely, any $k$-set with at least $t$ edges supplies such an edge set. The running time is bounded by $m^{O(t)}$ plus polynomial work per candidate.

This handles fixed $t$ exactly, including the fact that a support with fewer than $k$ vertices can be padded because $k\le n$. It does not give a polynomial-time algorithm when $t$ is an input of unbounded size. The same distinction applies to brute-force enumeration over $k$: a family of algorithms with exponents depending on a parameter is not a single polynomial-time algorithm on all instances.

6. Finite diagnostics and the remaining reduction problem.

The accompanying exact checks enumerate simple graphs through six vertices, calculate all $M_k$ by subset enumeration, and check the expectation lower bound and both monotonicities. They also run the conditional-expectation construction and compare its output with its promised rational bound. Separate formulas check the near-clique blow-up and complete-graph LP examples. These are checks of finite combinatorics and implementation; none is evidence of NP-hardness by itself.

A complete solution still needs a fixed $\varepsilon>0$ and a uniform deterministic transformation from an NP-hard language with three simultaneous guarantees: polynomial output size; a $k$-set attaining the yes threshold on every yes-instance; and a global bound strictly below $t/(1+\varepsilon)$ for every $k$-set on every no-instance. The last quantifier must control sets that mix portions of gadgets in unexpected ways. The ordinary clique reduction misses the quantitative gap, the simple blow-up preserves that miss, and the hypothetical product loses polynomial size. The partial algorithms above do not repair any of these three defects. No claimed constant-gap reduction is supplied here.

Sources

• S1 Bundit Laekhanukit, Pasin Manurangsi and Ohad Trabelsi, A Note on Approximability of Densest At-Least-k-Subgraph, arXiv:2605.25464v1 (25 May 2026). https://arxiv.org/html/2605.25464v1. Formulation source.