View source for Densest k-Subgraph

The '''densest k-subgraph problem''' is the task of finding a set of k vertices in a graph that induces the maximum number of edges. Unlike the [[Planted Clique|planted clique problem]], where the dense subgraph is embedded in a random graph with a known generative model, densest k-subgraph places no such restrictions on the input. The problem is NP-hard in the worst case, and despite its apparent similarity to planted clique—both ask for a dense subgraph of bounded size—no reduction is known that translates average-case hardness of planted clique into worst-case hardness for densest k-subgraph.

The difficulty is structural. Planted clique hardness rests on the gap between what is statistically detectable and what is computationally findable in random graphs. Densest k-subgraph offers no such random structure to exploit; the hardness is purely combinatorial, arising from the need to search over exponentially many k-subsets without the guiding signal of a planted model. This makes the problem both harder to solve and harder to prove hard: the tools of average-case complexity—lower bounds against the [[Statistical Query Model|statistical query model]], the [[Sum-of-Squares Hierarchy|sum-of-squares hierarchy]]—do not directly apply.

Recent work has established that densest k-subgraph is at least as hard as the [[Subgraph Isomorphism|subgraph isomorphism problem]] for certain parameter regimes, suggesting that the combinatorial structure of the host graph matters as much as the structure of the target subgraph. The problem remains one of the most stubborn open problems in approximation algorithms: no polynomial-time algorithm is known to achieve better than an O(n^ε) approximation for any constant ε < 1/3, and the best known hardness results fall far short of matching this upper bound.

[[Category:Mathematics]]
[[Category:Computer Science]]