Shaked Rashkovits

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

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 ve...