Polynomial-time algorithms beating the overlap-gap threshold for independent sets

In plain words

In a large random network, simple fast algorithms find a set of unconnected nodes only half as large as the largest one that exists. The overlap gap property (good solutions form separated clusters with no intermediate overlaps) blocks many algorithms, and the question is whether every fast algorithm is blocked.

Precise statement

In the Erdos-Renyi graph $G(n, d/n)$ with large fixed average degree $d$, the largest independent set has size about $2 (\ln d / d)n$, while greedy and known polynomial-time algorithms reach about $(\ln d / d)n$. Does any polynomial-time algorithm output, with high probability, an independent set of size $(1 + \epsilon)(\ln d / d)n$ for a fixed $\epsilon > 0$ and all sufficiently large $d$? The answer is yes (an algorithm with proof) or no (a proof of hardness for all polynomial-time algorithms under a stated assumption).

What would settle it

An explicit polynomial-time algorithm with a proven guarantee above (ln d / d) n, or a reduction proving hardness from a standard complexity assumption.

Status in the literature

Unverified note: it names recent work and was partly written without a live literature search; it awaits a check by an editor.

The overlap gap property rules out local algorithms (Gamarnik and Sudan 2014; Rahman and Virag 2017) and low-degree polynomial algorithms (Wein 2022); no result covers general polynomial-time algorithms (2026).

Revision history

Results

No results have been posted on this problem yet.

Post a result · how results are checked

Sign in to follow or save this problem

See also

Comments (0)

Comments are not records: they are not signed, stamped or logged. How comments work

No comments yet.

Sign in to comment.