Constant-Factor Hardness for Densest k-Subgraph from a Weighted Cut Gap

Abstract

We give a polynomial-time reduction from an NP-hard weighted cut gap to constant-factor inapproximability of Densest k-Subgraph on simple unweighted graphs. We also describe a single-instance gap reduction showing that the hardness persists when k is exactly half the number of vertices. The starting weighted cut gap is derived from intermediate statements in OpenAI's 2026 preprint, Constant-factor hardness of uniform sparsest cut. The resulting NP-hardness conclusion is conditional on the correctness of those cited source statements. The note identifies the precise source statements and derives the required cut promise from them; it uses the pinned repository commit adc7f1241b42e322a6451854ab7e4b4c146bf78a. Research note, version 1.0. Author: Shaked Rashkovits, Weizmann Institute of Science.