TY - GEN
T1 - Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph
AU - Bhaskara, Aditya
AU - Charikar, Moses
AU - Guruswami, Venkatesan
AU - Vijayaraghavan, Aravindan
AU - Zhou, Yuan
PY - 2012
Y1 - 2012
N2 - 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(n1/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 Ω(n1/4/log3 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 n2/53-ε on the integrality gap of nΩ(ε) rounds of the Lasserre SDP relaxation for Densest k-subgraph, and an nΩε(1) gap for n1-ε 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 n1/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.
AB - 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(n1/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 Ω(n1/4/log3 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 n2/53-ε on the integrality gap of nΩ(ε) rounds of the Lasserre SDP relaxation for Densest k-subgraph, and an nΩε(1) gap for n1-ε 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 n1/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.
UR - http://www.scopus.com/inward/record.url?scp=84860212454&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84860212454&partnerID=8YFLogxK
U2 - 10.1137/1.9781611973099.34
DO - 10.1137/1.9781611973099.34
M3 - Conference contribution
AN - SCOPUS:84860212454
SN - 9781611972108
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 388
EP - 405
BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
PB - Association for Computing Machinery
T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Y2 - 17 January 2012 through 19 January 2012
ER -