Densest-k-subgraph approximation

Pick exactly three dots from a network with four dots A, B, C and D. Its links are AB, AC, BC and CD. Picking A, C and D keeps two links; picking A, B and C keeps three, the most any three dots can have.

For larger networks, can one efficient rule always keep at least a fixed fraction of the best possible link count? The fraction must stay the same as the network and the requested group size grow.[1]

Can an efficient algorithm always choose a fixed-size group that captures a fixed fraction of the largest possible number of internal links? In the graph with edges AB, AC, BC and CD, selecting A, C and D gives two induced edges; selecting A, B and C gives three. Three is optimal because a simple graph on three vertices has at most three edges.

For a finite unweighted undirected simple graph, let $e(S)$ count induced edges, and let OPT be the largest such count among sets of exactly $k$ vertices. The desired approximation factor is one universal constant $C\ge1$, with $e(S)\ge\mathrm{OPT}/C$ for every input. Both the graph size and $k$ vary; the algorithm must run in polynomial time. If OPT is zero, the inequality simply requires a nonnegative count.[1]

No general constant-factor guarantee or matching impossibility result settles this.[2]

Known polynomial-time guarantees such as $n^{1/4+\varepsilon}$, for each fixed positive $\varepsilon$, still grow with the number $n$ of vertices. The cited result with factor $O(n^{1/4})$ uses quasipolynomial time. Neither establishes the constant polynomial-time guarantee.

The 2026 at-least-k paper assumes a Densest-k-Subgraph hardness statement for its conditional result. Its target allows larger selections and uses edges per selected vertex; it does not establish that assumed hardness or settle this exactly-k question.[1] [2]

A fixed group size makes this a question about concentration of links. Adding more dots could increase the link count without finding a tightly connected group, so the size budget is essential. A guarantee against the best group would measure how much of that concentration an algorithm can reliably capture.[1]

For a fixed size, maximizing the edge count also maximizes average internal degree: each internal edge contributes once at each end. Once the size can change, edge count and links per vertex need not rank groups in the same way. This explains why the size convention changes the optimization problem.

The approximation question isolates another distinction: exact optimization may be hard while a controlled loss remains possible. It asks how much local connectivity is algorithmically accessible, rather than how many links the entire network contains.[1] [2]