### Abstract

The Densest k-subgraph problem (i.e. find a size k 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 k-subgraph: the current best algorithm gives an ≈ O(n ^{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 k-subgraph and its variants. Thus, understanding the approximability of Densest k-subgraph is an important challenge. In this work, we give evidence for the hardness of approximating Densest k-subgraph within polynomial factors. Specifically, we expose the limitations of strong semidefinite programs from SDP hierarchies in solving Densest k-subgraph. Our results include: • A lower bound of Ω(n ^{1/4}/log ^{3} n) on the integrality gap for Ω(log n/log log n) rounds of the Sherali-Adams relaxation for Densest k-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. • For every ε > 0, a lower bound of n ^{2/53-ε} on the integrality gap of n ^{Ω(ε)} rounds of the Lasserre SDP relaxation for Densest k-subgraph, and an n ^{Ωε(1)} gap for n ^{1-ε} rounds. Our construction proceeds via a reduction from random instances of a certain Max-CSP over large domains. In the absence of inapproximability results for Densest k-subgraph, our results show that beating a factor of n ^{Ω(1)} is a barrier for even the most powerful SDPs, and in fact even beating the best known n ^{1/4} factor is a barrier for current techniques. Our results indicate that approximating Densest k-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 n ^{εΩ(1)} rounds of the Lasserre hierarchy, where ε is the completeness parameter in Unique Games and Small Set Expansion.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |

Pages | 388-405 |

Number of pages | 18 |

State | Published - Apr 30 2012 |

Externally published | Yes |

Event | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan Duration: Jan 17 2012 → Jan 19 2012 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|

### Other

Other | 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 |
---|---|

Country | Japan |

City | Kyoto |

Period | 1/17/12 → 1/19/12 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012*(pp. 388-405). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).