PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:1110.1360v1cs.DScs.CC

TL;DR

Densest k-subgraph has a large gap between its best approximation algorithm and known inapproximability results. This paper studies Sherali–Adams and Lasserre relaxations and proves polynomial integrality gaps at specified round counts.

  • Problem

    Densest k-subgraph has a large gap between the best approximation algorithm and known inapproximability results, despite its importance in optimization and average-case applications.

    Source: §1 · p. 2

  • Method

    The paper studies lift-and-project relaxations for Densest k-subgraph using the Sherali–Adams and Lasserre hierarchies.

    Source: §1 · p. 2

  • Results

    Ω(n^1/4/log^3 n) gap for Ω(log n/log log n) Sherali–Adams+ levels and Ω(n^2/53−ϵ) for n^Ω(ϵ) Lasserre levels.

    Source: §5 · p. 23

  • Takeaways & Limitations

    Natural Erdős–Rényi random graph instances can witness the Sherali–Adams+ integrality gap.

    Source: §1 · p. 2

    Matching integrality-gap lower bounds for n^Ω(ϵ) hierarchy levels remain an open goal.

    Source: §5 · p. 23

Abstract

from arXiv · show

The densest k-subgraph (DkS) 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 DkS: 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 DkS is an important challenge. In this work, we give evidence for the hardness of approximating DkS 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 Omega(n^{1/4}/log^3 n) on the integrality gap for Omega(log n/log log n) rounds of the Sherali-Adams relaxation for DkS. This also holds for the relaxation obtained from Sherali-Adams with an added SDP constraint. Our gap instances are in fact Erdos-Renyi random graphs. * For every epsilon > 0, a lower bound of n^{2/53-eps} on the integrality gap of n^{Omega(eps)} rounds of the Lasserre SDP relaxation for DkS, and an n^{Omega_eps(1)} gap for n^{1-eps} 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 DkS, our results show that even the most powerful SDPs are unable to beat a factor of n^{Omega(1)}, and in fact even improving the best known n^{1/4} factor is a barrier for current techniques.

1 Introduction

Densest k-subgraph has a substantial gap between its best known approximation algorithm and known hardness results, despite its relevance to applications and complexity research. This paper studies lift-and-project relaxations and gives integrality-gap evidence that strong SDP hierarchies have difficulty approximating the problem.

1 Introduction

  • The best known algorithm achieves an O(n^1/4+ε)-factor approximation, while known constant-factor hardness relies on assumptions stronger than P != NP.The problem also arises in community detection and protein-network analysis.Source: §1 · p. 2
  • The paper studies lift-and-project relaxations, whose successive levels strengthen mathematical-programming relaxations and can be solved in n^O(r) time after r levels.The best known O(n^1/4+ε) approximation uses an LP weaker than O(1/ε) Sherali-Adams levels.Source: §1 · p. 2
  • Sherali-Adams has an approximately Ω(n^1/4) integrality gap, while Lasserre has an Ω(n^(2/53−O(ε))) gap at polynomially many levels and a polynomial gap at almost-linear levels.The paper also notes that the Densest k-subgraph gaps are substantially stronger than the problem's then-known hardness bounds.Source: §1 · pp. 2–3
  • The gap instances include Erdős–Rényi random graphs and random bipartite graphs under a special distribution, so natural instance distributions are gaps with high probability.Source: §1 · p. 2
  • The results indicate that even the most powerful SDPs cannot beat an n^Ω(1) approximation factor, and that improving on n^1/4 is a barrier for current techniques.Source: §1 · p. 3
  • Densest k-subgraph may be harder to approximate within polynomial factors than Unique Games or Small Set Expansion, which have been shown solvable with n^{εΩ(1)} Lasserre rounds.Source: §1 · p. 3

2 Preliminaries

The preliminaries define the notation and describe three increasingly strong lift-and-project relaxations for Densest k-subgraph. Each hierarchy uses local information from subsets of vertices, and the paper’s integrality-gap results also apply to its minimum-degree Lasserre variant.

2.1 Notation.

  • For an induced subgraph H, d(H) denotes its average degree, and Γ_H(v) denotes the neighbors of v within H.The notation drops the H suffix when H is the full graph G.Source: §2.1 · p. 4

2.2 The relaxation hierarchies for Densest k-subgraph.

  • At r levels, Sherali-Adams and Lasserre solutions induce valid distributions on any set of r vertices, and the relaxations can be solved in n^O(r) time.The integrality gap becomes 1 after n levels.Source: §2.2 · p. 4

2.2.1 The Sherali-Adams LP hierarchy.

  • The Sherali-Adams hierarchy strengthens a basic LP with vertex and edge variables; the paper instead starts from a stronger minimum-degree LP, equivalent within a factor of 2.The basic LP uses x_i for vertex membership and x_ij for whether both endpoints of an edge are selected; the stronger LP seeks to maximize the induced minimum degree.Source: §2.2.1 · p. 4

2.2.2 The mixed hierarchy (Sherali-Adams + SDP).

  • The mixed hierarchy, SA+, adds a positive-semidefinite constraint requiring the edge variables x_ij to arise from vector inner products.This combines Sherali-Adams constraints with an SDP constraint.Source: §2.2.2 · p. 5

2.2.3 The Lasserre hierarchy.

  • Lasserre assigns a vector U_S to each vertex subset of size at most r, with vector lengths corresponding to Sherali-Adams LP values x_S.The intended vector is U_empty when every vertex in S is selected, and zero otherwise.Source: §2.2.3 · p. 5
  • The integrality gaps also hold for the Lasserre hierarchy with the minimum-degree SDP constraint, called the Min degree Lasserre SDP.The constraint captures a search for a k-subgraph with largest induced minimum degree.Source: §2.2.3 · p. 6

3 Integrality Gap for the Sherali-Adams hierarchy

The section constructs random-graph instances where Sherali–Adams has a large integrality gap, then shows the gap persists with a first-level SDP constraint. Its feasible solution is based on minimum Steiner-tree sizes and is verified using bounds on how those sizes change when a vertex is added.

3 Integrality Gap for the Sherali-Adams hierarchy

  • For k=n^1/2, the relaxation attains d=Ω(n^1/4/L), while every k-subgraph has density at most O(log^2 n).The construction establishes feasibility for L up to order log n/log log n.Source: §3 · p. 6, §3.1 · p. 6

3.1 The instance.

  • The instances are G(n,p) random graphs with p=n^-1/2 log n, where vertices have degree about n^1/2 log n and every pair has a common neighbor.The construction uses k=n^1/2; the stated graph properties hold with high probability.Source: §3.1 · pp. 6–7

3.2 Feasible solution.

  • The feasible assignment sets x_S according to the size of a minimum Steiner tree spanning S, with dampening factors to control the hierarchy constraints.The intuition starts with equal singleton values and assigns larger values when adding a vertex increases the minimum Steiner-tree size less.Source: §3.2 · p. 7

3.3 The Size Constraint and Minimum Steiner trees in G(n, p).

  • Bounds on vertices that leave the Steiner-tree size unchanged or increase it by one control the sum of x_{S∪i} and verify the size constraint.The section bounds these counts by (2|S| log n)^{2|S|} and (4|S| log n)^{4|S|} × n^1/2, respectively.Source: §3.3 · pp. 9–11

3.4 Gaps for the mixed hierarchy (SA+).

  • Adding a first-level SDP constraint does not remove the gap: the mixed hierarchy still has an integrality gap of ˜Ω(n^1/4).The positive semidefinite condition is satisfied by the same solution with high probability.Source: §3.4 · p. 11

4 Integrality Gap for the Lasserre hierarchy

This section constructs Densest k-subgraph Lasserre integrality gaps via reductions from random Max K-CSP instances, using high-probability completeness, soundness, and constraint-expansion guarantees. It establishes an Ω(q) gap for a specified number of levels and a maximized exponent of 2/53 − O(κ), including polynomial-round relaxations.

4 Integrality Gap for the Lasserre hierarchy

  • Extending [Tul09] to superconstant K, random Max K-CSP instances admit perfect solutions for ηn/16 Lasserre rounds under Theorem 4.2’s parameter conditions, with probability 1−o(1).The proof establishes high left-expansion: every set of 2 ≤ s ≤ ηn constraints involves more than (K−δ)s variables.Source: §4 · pp. 12–13

4.2 The Lasserre gap for Densest k-subgraph.

  • The reduction turns Max K-CSP constraints and satisfying assignments into a bipartite graph, duplicates right-side variable-assignment vertices, and sets the Densest k-subgraph target to k = 2m.The construction uses a dual q-ary code with distance at least 3; the cited generalized BCH codes have block length K = q^2−1 and dimension K−4δ+3.Source: §4.2 · p. 13

4.3 Analysis.

  • The gap is N^(2/53−O(κ)) for the N^κ-round Min degree Lasserre SDP, while Theorem 4.7 gives Ω(q) for N/q^O(1) levels.Theorem 4.7 also applies to the Min degree Lasserre SDP when q = Ω(log n) and q < N^ε.Source: §4.3 · p. 14
  • For the reduction, a perfect r-round Max K-CSP solution yields a Densest k-subgraph Lasserre solution of value βmK after r/K rounds.With probability 1−o(1), every subgraph with 2m left and 2m right vertices has at most 17βmK/q edges, yielding an Ω(q) gap.Source: §4.3 · p. 14, Completeness · p. 15, Soundness · p. 18
  • By combining Theorem 4.2, Lemmas 4.9, 4.11 (completeness), and 4.12 (soundness), with probability 1 − o(1), graph G′Φ provides an Ω(q) integrality for the number of levels R.Source: Soundness · p. 20

4.4 Expansion for random Max K-CSP instances.

  • With probability 1 − o(1), every set of s constraints, for 2 ≤ s ≤ ηn, involves more than (K − δ)s variables.This is the expansion property established for the random Max K-CSP instances.Source: §4.4 · p. 21

5 Conclusion

The paper establishes polynomial integrality gaps for Sherali-Adams+ and Lasserre relaxations of Densest k-subgraph, including gaps on random graph instances. It leaves open whether comparable gaps hold for stronger Sherali-Adams relaxations or polynomial-level Lasserre relaxations.

5 Conclusion

  • Ω(n^1/4/log^3 n) gaps hold for Ω(log n/log log n) levels of Sherali-Adams+ SDP for Densest k-subgraph.The gap instances are Erdős–Rényi random graphs.Source: §5 · p. 23
  • Ω(n^2/53−ε) gaps hold for n^Ω(ε) levels of the Lasserre SDP relaxation for Densest k-subgraph.The conclusion identifies obtaining Ω(n^1/4−ε) gaps for polynomial Lasserre levels as a further goal.Source: §5 · p. 23
  • The authors leave open matching integrality-gap lower bounds for n^Ω(ε) levels and stronger Sherali-Adams relaxations.They also suggest combining techniques from both parts of the paper to seek Ω(n^1/4−ε) gaps for polynomial Lasserre levels.Source: §5 · p. 23

A Random graph properties

For G(n,p) with p = n^−1/2(log n)^1/2, the stated graph properties hold with high probability. These include degree and common-neighbor bounds, and a density bound for induced subgraphs of size n^1/2.

A Random graph properties

  • Every vertex has degree between (n^1/2 log n)/2 and 2n^1/2 log n with high probability.The proof uses the expected degree n^1/2 log n and a Chernoff bound followed by a union bound.Source: A Random graph properties · pp. 26–27
  • Every pair of vertices has at most 2 log^2 n common neighbors with high probability.The proof bounds the expected number of common neighbors by log^2 n.Source: A Random graph properties · pp. 26–27
  • Every pair of vertices has at least one common neighbor with high probability.The proof uses an expected common-neighbor count of log^2 n and a union bound.Source: A Random graph properties · pp. 26–27
  • No induced subgraph on n^1/2 vertices has density greater than 5 log n with high probability.The appendix states this property for the same random graph setting.Source: A Random graph properties · pp. 26–27
Loading 1110.1360v1…