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

Aditya Bhaskara, Moses Charikar, Venkatesan Guruswami, Aravindan Vijayaraghavan, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish (US)
Title of host publicationProceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
Pages388-405
Number of pages18
StatePublished - Apr 30 2012
Externally publishedYes
Event23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012 - Kyoto, Japan
Duration: Jan 17 2012Jan 19 2012

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

Other

Other23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012
CountryJapan
CityKyoto
Period1/17/121/19/12

Fingerprint

Integrality
Subgraph
Hardness
Polynomials
Polynomial
Approximation algorithms
Game
Lower bound
Inapproximability
Semidefinite Program
Approximability
Random Graphs
Approximation Algorithms
Upper and Lower Bounds
Completeness

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Cite this

Bhaskara, A., Charikar, M., Guruswami, V., Vijayaraghavan, A., & Zhou, Y. (2012). Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. In 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).

Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. / Bhaskara, Aditya; Charikar, Moses; Guruswami, Venkatesan; Vijayaraghavan, Aravindan; Zhou, Yuan.

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Bhaskara, A, Charikar, M, Guruswami, V, Vijayaraghavan, A & Zhou, Y 2012, Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 388-405, 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012, Kyoto, Japan, 1/17/12.
Bhaskara A, Charikar M, Guruswami V, Vijayaraghavan A, Zhou Y. Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. In Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 2012. p. 388-405. (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
Bhaskara, Aditya ; Charikar, Moses ; Guruswami, Venkatesan ; Vijayaraghavan, Aravindan ; Zhou, Yuan. / Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph. Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012. 2012. pp. 388-405 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).
@inproceedings{be875287b5bf4321af574a6a54d66f60,
title = "Polynomial integrality gaps for strong SDP relaxations of Densest k-subgraph",
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{\"o}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.",
author = "Aditya Bhaskara and Moses Charikar and Venkatesan Guruswami and Aravindan Vijayaraghavan and Yuan Zhou",
year = "2012",
month = "4",
day = "30",
language = "English (US)",
isbn = "9781611972108",
series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",
pages = "388--405",
booktitle = "Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012",

}

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/4/30

Y1 - 2012/4/30

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

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

UR - http://www.scopus.com/inward/record.url?scp=84860212454&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860212454&partnerID=8YFLogxK

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

ER -