Source-linked AI summary
Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph
Pasin Manurangsi
TL;DR
Densest k-Subgraph has limited known hardness despite widespread belief that stronger inapproximability should hold. This work uses a subexponential-time reduction from gap 3SAT to establish almost-polynomial hardness under ETH and Gap-ETH, while leaving polynomial-ratio hardness unresolved.
Problem
Densest k-Subgraph lacks even constant-factor NP-hardness, and existing lower bounds have not established polynomial-ratio hardness.
Method
The paper provides a subexponential-time reduction from the gap version of 3SAT to Densest k-Subgraph.
Results
Under ETH, no polynomial-time algorithm can distinguish the theorem’s two cases at ratio N^(1/(log log N)^c) for a constant c>0, while Gap-ETH yields hardness for ratios N^f(N) with f in o(1).
Takeaways & Limitations
The results establish almost-polynomial hardness of approximation for Densest k-Subgraph, including perfect completeness, but do not settle polynomial-ratio hardness.
Takeaways & Limitations
Polynomial-ratio hardness and constant-factor NP-hardness for Densest k-Subgraph remain open.
Abstract
from arXiv · showhide
In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio (Bhaskara et al., 2010), previous attempts at proving hardness of approximation, including those under average case assumptions, fail to achieve a polynomial ratio; the best ratios ruled out under any worst case assumption and any average case assumption are only any constant (Raghavendra and Steurer, 2010) and $2^{Ω(\log^{2/3} n)}$ (Alon et al., 2011) respectively. In this work, we show, assuming the exponential time hypothesis (ETH), that there is no polynomial-time algorithm that approximates Densest $k$-Subgraph to within $n^{1/(\log \log n)^c}$ factor of the optimum, where $c > 0$ is a universal constant independent of $n$. In addition, our result has "perfect completeness", meaning that we prove that it is ETH-hard to even distinguish between the case in which $G$ contains a $k$-clique and the case in which every induced $k$-subgraph of $G$ has density at most $1/n^{-1/(\log \log n)^c}$ in polynomial time. Moreover, if we make a stronger assumption that there is some constant $\varepsilon > 0$ such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only $(1 - \varepsilon)$-satisfiable (also known as Gap-ETH), then the ratio above can be improved to $n^{f(n)}$ for any function $f$ whose limit is zero as $n$ goes to infinity (i.e. $f \in o(1)$).
1 Introduction
Densest k-Subgraph remains difficult to approximate: the best general algorithm achieves O(n^1/4+ε), while prior hardness results ruled out only constant or subpolynomial ratios. This work proves almost-polynomial ETH-hardness with perfect completeness, strengthened to n^f(n) under Gap-ETH.
- Problem definition: Densest k-Subgraph asks for k vertices inducing the maximum number of edges, equivalently maximizing induced-subgraph density because k is fixed.The paper uses density |E(S)|/choose(k,2), which lies in [0,1].
- Approximation algorithms: O(n^1/4+ε) remains the best known polynomial-time approximation ratio for general Densest k-Subgraph.Earlier algorithms achieved O~(n^0.3885) and O(n^1/3−δ) ratios before the log-density approach.
- Prior hardness: Prior hardness results ruled out any constant ratio under worst-case assumptions and 2^O(log^2/3 n) under an average-case assumption, while polynomial-ratio hardness remained open.Known results also included constant-factor hardness from strengthened Unique Games and related hypotheses.
- Our results: Theorem 1 rules out polynomial-time n^1/(log log n)^c approximation under ETH, even when distinguishing a k-clique from k-subgraphs of density at most n^-1/(log log n)^c.This is a perfect-completeness result: the YES case contains an induced k-clique.
- Our results: Under Gap-ETH, Theorem 2 strengthens the ruled-out ratio to n^f(n) for every f in o(1), with the same perfect-completeness distinction.The result transfers to several related problems, including Densest At-Most-k-Subgraph, Smallest m-Edge Subgraph, Steiner k-Forest, and Quadratic Knapsack.
- Scope and limitations: The ratios cannot be improved to a fixed polynomial under perfect completeness because an n^ε-approximation runs in time n^O(1/ε), and Densest k-Subgraph remains open for constant-factor NP-hardness.The conclusion also notes that no polynomial-ratio hardness result is known.
2 Preliminaries and Notations
The preliminaries fix notation for graphs, subsets, density, and labelled bicliques, then state ETH, Gap-ETH, PCP foundations, and the subexponential-time reduction perspective used later.
- Notation: The paper uses exp(x) for e^x, log(x) for log_2(x), and polylog n for O(log^c n) for a constant c.
- Notation: For a set S, P(S) is its power set, while the size-t subset family collects all T ⊆ S with |T| = t.
- Graph notation: Graphs are simple, unweighted, and undirected; density is the edge count divided by the number of possible edges, and α-dense means density α.
- Graph notation: A labelled copy of K_t,t is an ordered pair (L,R) of t-size multisets whose distinct cross-pairs are edges, and all such pairs are counted.
- Exponential-time hypotheses: ETH asserts that no 2^o(m)-time algorithm decides satisfiability for arbitrary 3SAT formulas with m clauses, while Gap-ETH strengthens this to distinguishing satisfiable formulas from those with val(φ) ≤ 1 − ε.
- PCPs and reductions: The PCP framework preserves completeness and creates constant soundness gaps, while Dinur’s version additionally gives bounded variable degree and nearly-linear size blow-up.
- PCPs and reductions: Nearly-linear PCPs enable subexponential-time reductions from gap-3SAT under ETH, including birthday-repetition constructions that support hardness results for other problems.
3 The Reduction and Proofs of The Main Theorems
The reduction maps bounded-occurrence 3SAT instances to Densest k-Subgraph using vertices representing partial assignments and edges encoding consistency. A biclique-counting argument bounds sound-case density, yielding the ETH- and Gap-ETH-based hardness results.
- Reduction: The reduction constructs Gφ,ℓ from a 3SAT formula, with vertices representing partial assignments to ℓ distinct variables.Two vertices are connected when their partial assignments are consistent and jointly satisfy every clause whose variables they cover.
- Reduction: A satisfying assignment induces a clique, providing perfect completeness for the constructed Densest k-Subgraph instance.
- Soundness: Alon’s lemma converts density into many labelled bicliques, while the reduction-specific counting lemma shows that sound instances contain too few such bicliques.
- Hardness consequences: Under ETH, the soundness bound becomes N^−1/(log log N)^(3ζ+9), ruling out the corresponding polynomial-time distinguisher.
- Hardness consequences: Under Gap-ETH, choosing ℓ from an arbitrary f ∈ o(1) yields soundness at most N^−f(N), establishing the stronger almost-polynomial hardness.
4 Conclusion and Open Questions
The paper establishes almost-polynomial hardness for Densest k-Subgraph but leaves polynomial-ratio hardness unresolved. It identifies the sliding scale conjecture as a plausible barrier and asks whether the construction extends to other approximation problems.
- Conclusion: The reduction gives almost-polynomial hardness under ETH and Gap-ETH, but Densest k-Subgraph still lacks known constant-factor NP-hardness and polynomial-ratio hardness.
- Open questions: Achieving polynomial-ratio hardness may require proving the sliding scale conjecture, which remains unknown even for Label Cover under ETH or Gap-ETH.
- Open questions: The authors ask whether their construction can establish inapproximability for Sparsest Cut, Min Bisection, Balanced Separator, Minimum Linear Arrangement, and 2-Catalog Segmentation.
A A Counterexample to Obtaining a Subconstant Soundness from Non-Boolean CSPs
The counterexample shows why non-boolean CSPs cannot directly provide the desired soundness: a low-value instance can produce a large biclique in the reduction graph. Random 2-XOR constraints yield value near one-half, limiting the attainable gap to two in this construction.
- Construction: For a non-boolean 2CSP, vertices encode ℓ-tuples of variable assignments over alphabet Σ, and the reduction graph contains a large biclique across two variable halves.
- Construction: The two sides form a biclique because there are no cross-half constraints and each selected vertex contains variables from only one half.
- Limitation: Random 2-XOR constraints on each side give val(φ) ≤ 1/2 + O(1/d), so the largest gap obtainable from this non-boolean construction is only two.
- Limitation: The example uses two disconnected components, leaving open whether stronger starting CSP structure, such as expansion, could yield a gap larger than two.