Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph

<p>The Densest <em>k</em>-subgraph problem (i.e. find a size <em>k</em> subgraph with maximum number of edges), is one of the notorious problems in approximation algorithms. There is a significant gap between known upper and lower bounds for Densest <em>k</em>-subgraph: the current best algorithm gives an ≈ <em>O</em>(<em>n</em>^1/4) approximation, while even showing a small constant factor hardness requires significantly stronger assumptions than P ≠ NP. In addition to interest in designing better algorithms, a number of recent results have exploited the conjectured hardness of Densest <em>k</em>-subgraph and its variants. Thus, understanding the approximability of Densest <em>k</em>-subgraph is an important challenge.</p> <p>In this work, we give evidence for the hardness of approximating Densest <em>k</em>-subgraph within polynomial factors. Specifically we expose the limitations of strong semidefinite programs from SDP hierarchies in solving Densest <em>k</em>-subgraph. Our results include:</p> <ul> <li> <p>A lower bound of Ω(<em>n</em>^1/4/log³ <em>n</em>) on the integrality gap for Ω(log <em>n</em> / log log <em>n</em>) rounds of the Sherali-Adams relaxation for Densest <em>k</em>-subgraph. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdös-Renyi random graphs.</p> </li> <li> <p>For every ∊ > 0, a lower bound of <em>n</em>^{2/53 − ∊} on the integrality gap of <em>n</em>^Ω(∊) rounds of the Lasserre SDP relaxation for Densest <em>k</em>-subgraph, and an <em>n</em>^Ω∊⁽¹⁾ gap for <em>n</em>^1−∊ rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains.</p> </li> </ul> <p>In the absence of inapproximability results for Densest <em>k</em>-subgraph, our results show that beating a factor of <em>n</em>^Ω(1) is a barrier for even the most powerful SDPs, and in fact even beating the best known <em>n</em>^1/4 factor is a barrier for current techniques.</p> <p>Our results indicate that approximating Densest <em>k</em>-subgraph within a polynomial factor might be a harder problem than Unique Games or Small Set Expansion, since these problems were recently shown to be solvable using <em>n</em>^{∊^ω(1)} rounds of the Lasserre hierarchy where ∊ is the completeness parameter in Unique Games and Small Set Expansion.</p>