ETH Hardness for Densest-k-Subgraph with Perfect Completeness
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Claim: under ETH there is no quasi‑polynomial algorithm for Densest‑k‑Subgraph with perfect completeness; the reduction blows up to about 2^{√n} vertices and matches known quasi‑poly upper bounds. Construction makes vertices = assignments to √n variable subsets, places edges for consistency and CSP constraint satisfaction using birthday repetition. Soundness is proved by an entropy counting argument: any large dense k‑subgraph either encodes a near‑global assignment (caught by intersections) or yields many consistency violations, so it cannot exist.
AI-written summary · about