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

Introduction

The densest $k$-subgraph problem takes as input a graph $G(V,E)$ on $n$ vertices and a parameter $k$, and asks for a subgraph of $G$ on at most $k$ vertices having the maximum number of edges. While it is a fundamental graph optimization problem and arises in several applications (community detection in social networks, identifying protein families and molecular complexes in protein-protein interaction networks, etc), there is a huge gap between the best approximation algorithm and the known inapproximability results. The current best approximation algorithm due to [BCC+10] gives $O(n^{1/4+\varepsilon})$-factor approximation algorithm which runs in time $n^{O(1/\varepsilon)}$ for any constant $\varepsilon>0$. On the inapproximability side, [Fei02] initially showed a small constant factor inapproximability for Densest $k$-subgraph using the random 3-SAT assumption. [Kho04] used quasi-random PCPs to rule out a PTAS. More recently, [RS10, AAM+10] used more non-standard assumptions to rule out any constant factor approximation algorithms.

While only constant factor approximations have been ruled out, it is commonly believed that Densest $k$-subgraph is much harder to approximate even on average (for a natural distribution on hard instances). Recently, average-case hardness assumptions based on the hardness of “planted” versions of Densest $k$-subgraph were used for public key cryptography [ABW08] and in showing that financial derivates can be fraudulently priced without detection [ABBG10]. Given the interest in Densest $k$-subgraph from both the algorithms and the complexity point of view, developing a better understanding of the problem is an important challenge for the field.

In this work, we study lift-and-project relaxations for Densest $k$-subgraph. Lift-and-project methods are systematic iterative procedures to obtain sequences of increasingly stronger mathematical programming relaxations for an integer optimization problem (e.g. Lovász-Schrijver [LS91], Sherali-Adams [SA90] and Lasserre [Las01]. See the survey by Laurent [Lau03] for a comparison). Typically, the relaxation obtained after $r$ levels of these strengthenings can be solved in $n^{O(r)}$ time. A number of recent papers have studied the strength and limitations of such relaxations as a basis for designing approximation algorithms for various problems [ABLT06, CMM09, Chl06, CS06, dVM07, GMPT07, GMT09, KS09, RS09, Sch08, STT07a, STT07b, Tul09] (see the recent survey by Chlamtac and Tulsiani [CT11]). In most cases of approximation algorithms that use strengthened LP and SDP relaxations, such relaxations can be obtained from a few levels of such lift-and-project procedures. In fact, the $O(n^{1/4+\varepsilon})$ approximation algorithm of [BCC+10] for Densest $k$-subgraph uses a linear programming relaxation which is weaker than that obtained from $O(1/\varepsilon)$ levels of the Sherali-Adams hierarchy.[BCC+10] also gives a purely combinatorial algorithm that does not use a linear program. [BCC+10] also show that the integrality gap becomes $O(n^{1/4-\varepsilon})$ after $n^{O(\varepsilon)}$ levels of the Sherali Adams LP hierarchy.

Our gap instances are actually (Erdös - Renyi) random graph instances $\mathcal{G}(n,p)$ and random bipartite graphs under a special distribution – hence, we show that natural distributions of instances are integrality gap instances with high probability.

We note that prior results exhibiting gap instances for lift-and-project relaxations do so for problems that are already known to be hard to approximate under some suitable assumption; based on this hardness result, one would expect lift-and-project relaxations to have an integrality gap that matches the inapproximability factor.

Our gap constructions for Densest $k$-subgraph in this paper are a rare exception to this trend, as the integrality gaps we show are substantially stronger than the (very weak) hardness bounds known for the problem. In fact, we are only aware of the following examples where a polynomial-round Lasserre integrality gap stronger than the corresponding NP-hardness result is known : Max $K$-CSP, $K$-coloring [Tul09], Balanced Separator and Uniform Sparsest Cut [GSZ11]. In the first two cases, NP-hardness results that are not that far from the gaps are known [ST00, Kho02] and for Max $K$-CSP a matching Unique-Games hardness is also known [ST09]. For the other two problems, constant factor integrality gaps were shown for linear number of rounds of Lasserre hierarchy [GSZ11]. Again, while these problems are not known to be APX-hard, under the conjectured intractability of Small Set Expansion, they are known to be hard to approximate within any constant factor.

In the absence of inapproximability results for Densest $k$-subgraph, our results show that beating a factor of $n^{\Omega(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. These results are perhaps indicative of the hardness of approximating Densest $k$-subgraph within $n^{\Omega(1)}$ factors.

A problem related to Densest $k$-subgraph is the Small Set Expansion (SSE) problem, which has received a lot of recent attention due to strong connections to the Unique Games conjecture [RS10]. One way to state the SSE conjecture [RS10] (which is known to imply the Unique Games conjecture) is as follows: for all $\epsilon>0$, there exists $\delta,D$ (think of $D$ as a constant), such that the following problem is not polynomial-time solvable:

Given a $D$-regular instance $G(V,E)$ with $k=\delta n$, the Gap-SSE problem is to distinguish between the following two cases.

Yes case. There exists a subgraph of $k$ vertices with average degree at least $(1-\varepsilon)D$.

No case. All subgraphs of $k$ vertices have average degree at most $\varepsilon D$.

Clearly, Densest $k$-subgraph is hard to approximate within any constant factor, assuming the Small Set Expansion conjecture. On the other hand, our results indicate that approximating Densest $k$-subgraph even within a polynomial factor may be a harder problem than Unique Games or Small Set Expansion, because these problems were recently shown to be solvable using $n^{\epsilon^{\Omega(1)}}$ rounds of the Lasserre hierarchy, where $\epsilon$ is the completeness parameter in Unique Games and Small Set Expansion [BRS11, GS11].

Preliminaries

We introduce some notation which will be used throughout the paper. $G=(V,E)$ refers to a graph which is an instance of the Densest $k$-subgraph problem on $n$ vertices, and $k$ refers to the size of the subgraph we are required to output. For an induced subgraph $H\subseteq G$, we denote by $d(H)$ the average degree (or density of $H$). For a vertex $v$ in subgraph $H$, we will denote by $\Gamma_{H}(v)$ the set of neighbors of $v$ in $H$ (the suffix will be dropped when $H=G$).

The phrase “with high probability” will mean: with probability $1-\frac{1}{p(n)}$, for any polynomial $p(n)$.

2 The relaxation hierarchies for Densest k𝑘k-subgraph.

We will be concerned with the SDP relaxations derived from the Sherali-Adams and Lasserre hierarchies for Densest $k$-subgraph. As in other lift-and-project schemes, a feasible solution to $r$ levels of these hierarchies satisfies the condition that for any set of $r$ vertices, it defines a valid distribution over integral solutions for these vertices – in particular, the integrality gap becomes $1$ after $n$ levels. Further, the relaxations given by $r$ levels of the Sherali-Adams and Lasserre hierarchies can be solved in $n^{O(r)}$ time. We are interested in the integrality gap of $r$ levels of these relaxations for Densest $k$-subgraph. Refer to [CT11] for a more comprehensive comparison of these relaxation hierarchies.

The Sherali-Adams hierarchy starts with a simple LP relaxation of a $\{0,1\}$ integer program, and obtains a sequence of successively tighter relaxations with more levels. The natural LP relaxation for Densest $k$-subgraph (LP1 in Figure 1) [SW98, FS97] has variables $\{x_{i}\}$ to denote if vertex $i$ belongs to the solution, and edge variables $\{x_{ij}\}_{\begin{subarray}{c}(i,j)\in E(G)\end{subarray}}$ to denote if both $i,j$ are in the subgraph. This LP has an integrality gap of $\Omega(\frac{n}{k})$ ([FKP01, FS97]).

For our integrality gaps, we will in fact start with a stronger basic (first-level) linear program (LP2 in Figure 1) which is equivalent upto a factor of $2$ (see [BCC+10]). Intuitively, it tries to find a $k$-subgraph $H$ where the minimum degree $d_{H}$ is maximized. An LP hierarchy obtained from this min. degree LP (LP2) was in fact used by [BCC+10] to obtain their approximation algorithm. While the program as stated is not linear, we guess the degree $d$ and consider the feasibility linear program that is obtained.

Let us consider strengthening this LP by considering $r$ levels of the Sherali-Adams hierarchy ($SA_{r}$, shown in Figure 2). In the lifted LP, the variable $x_{S}$ is supposed to capture whether every vertex in $S$ belongs to the chosen $k$-subgraph (i.e., $x_{S}=\prod_{i\in S}x_{i}$). Further if we take two sets $S,S^{\prime}$ of $\leq r$ vertices, the local distributions induced by a feasible solution (using the inclusion-exclusion constraints), agree on the variables in the intersection $S\cap S^{\prime}$. We follow the notation established in [CT11] while defining the hierarchy.

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

The mixed hierarchy (also refered to as SA+) imposes an additional SDP constraint on top of the Sherali-Adams LP relaxation. In particular, it asks for the values $x_{ij}$ to come from vector inner products i.e. the matrix $X=(x_{ij})$ is p.s.d. Most known algorithms which proceed by rounding a relaxation obtained from an SDP hierarchy [Chl06, CS06, BRS11] work with this mixed hierarchy [GS11] is an exception and seems to need a relaxation given by the Lasserre hierarchy..[RS09, KS09] and [GMT09] considered this hierarchy and obtained integrality gaps for Unique Games and approximation-resistant CSPs.

One level of the mixed hierarchy for Densest $k$-subgraph gives the SDP relaxation introduced in [FS97, SW98]. [BCC+10] show that the mixed hierarchy performs better than log-density based arguments (which are captured by just the LP hierarchy) in a planted model.In particular, the problem of detecting if dense $k$-subgraph is planted in a random graph or not, in the parameter range $D<n^{1/2}$. It is interesting in this light to obtain integrality gaps for mixed hierarchy.

2.3 The Lasserre hierarchy.

The Lasserre hierarchy produces a sequence of SDP relaxations which are stronger than the Sherali-Adams and the mixed hierarchies. As in [CT11], the $r$-level Lasserre SDP for Densest $k$-subgraph introduces a vector ${\bm{U}}_{S}$ for each subset $S\subseteq V$ with $|S|\leq r$ (Figure 3).

The intended solution sets ${\bm{U}}_{S}={\bm{U}}_{\emptyset}$ if every vertex in $S$ belongs to the densest $k$-subgraph, and ${\bm{U}}_{S}=\bf{0}$ otherwise. The vector lengths $\left\lVert{\bm{U}}_{S}\right\rVert^{2}$ correspond to valid LP values $x_{S}$ for the Sherali-Adams relaxation presented above.

As in Section 2.2.1, we can write an SDP which tries to find the $k$-subgraph of largest induced minimum degree $d$. This can be captured by the SDP constraint (analogous to (2))

However, we show in Section 4.3 that our integrality gaps also hold for the Lasserre hierarchy defined by this SDP. We refer to the SDP with constraint (4) as the Min degree Lasserre SDP .

Integrality Gap for the Sherali-Adams hierarchy

In what follows $L$ will denote the number of levels of the hierarchy we will consider.

Let $L\leq\frac{\log n}{10\log\log n}$. The integrality gap of $\text{SA}_{L}$ is at least \Omega\big{(}\frac{n^{1/4}}{L\log^{2}n}\big{)}.

To prove Theorem 3.1, we present instances $G$ where the relaxation has a solution with value $d=\Omega(n^{1/4}/L)$, while the integer optimum, i.e., the largest density of a $k$-subgraph in $G$ is only $O(\log^{2}n)$. It will be notationally convenient to construct gaps for $L/2$ levels.

We in fact give a distribution over instances, and prove that the desired gap holds with high probability. The instances we consider are $\mathcal{G}(n,p)$ random graphs with $p=n^{-1/2}\log n$ (thus the expected degree of each vertex is $D=n^{1/2}\log n$). The parameter $k$ is chosen to be $n^{1/2}$. An easy calculation shows that in any $k$ subgraph, the density (and hence the min-degree) is at most $O(\log^{2}n)$ (see full version or [BCC+10, FKP01]). The meat of the argument is thus to show that there exists an LP solution to $\text{SA}_{L/2}$ (Equations (1)-(3)) of value $d=\Omega(n^{1/4}/L)$ even for $L$ of the order $\log n/\log\log n$.

The following are the properties of the distribution $\mathcal{G}(n,p)$ (with above parameters) we will truly be using [see Section A for proofs]. Any graph with these properties admits the solution to $\text{SA}_{L/2}$ which we describe.

Every vertex has degree between $(n^{1/2}\log n)/2$ and $2n^{1/2}\log n$.

Any two vertices $i,j$ have at least one common neighbor and has at most $O(\log^{2}n)$ common neighbours.

2 Feasible solution.

Before formally giving the $x_{S}$ values, we give intuition as to what they ought to be. First, we start out setting $x_{i}=n^{-1/2}$ (equal for all vertices, since $\sum_{i}x_{i}\leq k=n^{1/2}$ and no vertex is special). Next, suppose $S\subset V$ with $i\in S$ and think of $d\approx n^{1/4}$. Now (2) implies that $\sum_{j\in\Gamma(i)}x_{S\cup j}\geq n^{1/4}x_{S}$. Further from (1), we obtain $\sum_{j\in V}x_{S\cup j}\leq n^{1/2}x_{S}$. Thus we conclude that $x_{S\cup j}$ must be roughly $n^{-1/4}x_{S}$ for $j\in\Gamma(S)$, while for $j\not\in\Gamma(S)$, it should be only $n^{-1/2}x_{S}$. Now consider $T\subset V$ which span a tree: we could imagine starting with one vertex and adding vertices one by one (each added vertex is a neighbour of the previous ones), and thus conclude that $x_{T}$ is roughly $n^{-(|T|+1)/4}$ (since $x_{i}=n^{-1/2}$ to begin with). Now let $S$ be an arbitrary set of vertices and consider a tree $T\supseteq S$: by monotonicity (a corollary of (3)), $x_{S}\geq x_{T}$, and since this is true for every such $T$, we need to set $x_{S}$ to be at least $n^{-(\mathsf{st}(S)+1)/4}$, where $\mathsf{st}(S)$ is the number of vertices (size) in the minimum Steiner tree of $S$.

These, with additional ‘dampening’ factors ($L$-terms), are precisely the values we will set. More precisely we consider the solution

where $\mathsf{st}(S)$, as above, is the size of the minimum Steiner tree of $S$. Thus for instance $x_{i}=n^{-1/2}/L$, while $x_{\{i,j\}}=1/(n^{3/4}L^{2})$ when $(i,j)\in E$ and $1/(nL^{2})$ otherwise (the latter is because there is a path of length-2 between any $i,j\in G$ with high probability).

Let us fix $L\leq\log n/(10\log\log n)$. We now show that the LP solution presented above is feasible for $\text{SA}_{L/2}$ with high probability. The following lemma is useful in simplifying the analysis: it implies that we need to only consider $T=\emptyset$ while showing that the LP solution satisfies constraints (1) and (2). This is where the ’dampening’ factors come into play.

Let $S,T$ be disjoint subsets of $V$ of size at most $t$ and $x_{S}$ be the solution described above. Then

One property of the assignment (5) is that $x_{S\cup i}\leq x_{S}/L$ for $i\not\in S$. Further all the $x_{S}$ are $\geq 0$, and thus in the sum above, the term corresponding to $J\subseteq T$ contibutes positively when $|J|$ is even and negatively otherwise. Hence,

A similar proof shows the upper bound, since the $x_{S\cup\{i\}}$ terms for $i\in T$ dominate the contributions of $x_{S\cup J}$ for $|J|>1$. ∎

In checking feasibility, it suffices to check (1) and (2) with $T=\emptyset$.

Lemma 3.2 allows us to ‘remove’ the $\sum_{J\subseteq T}$ on both sides of the equations (and set $T=\emptyset$) by losing a factor of 2. Since we allow constant slack, the claim follows. ∎

We refer to the constraints (1) and (2) as the size and the density constraints respectively, because the former says that we should pick only a $k$-subgraph, and the latter says the minimum degree (density) is at least $d$. The assignment we described allows us to prove the density constraint easily.

(Density Constraint) The $x_{S}$ described above satisfy constraints (2).

Let $S\subset V$ and $i\in S$. We need to check that $\sum_{j\in\Gamma(i)}x_{S\cup j}\geq\frac{n^{1/4}}{L}\cdot x_{S}$. It is easy to see that for every $j\in\Gamma(i)$, $\mathsf{st}(S\cup j)\leq\mathsf{st}(S)+1$, and thus $x_{S\cup j}\geq\frac{n^{-1/4}}{L}\cdot x_{S}$ (the $L$ term is due to the dependence on $|S|$ in (5)). Since there are at least $n^{1/2}\log n/2$ terms in the LHS, the inequality follows. ∎

3 The Size Constraint and Minimum Steiner trees in 𝒢​(n,p)𝒢𝑛𝑝\mathcal{G}(n,p).

By the above corollary, it suffices to check (noting $k=n^{1/2}$) that

We show this by proving that $\mathsf{st}(S\cup i)\geq\mathsf{st}(S)+2$ for most $i\in V$, in particular we bound the number of exceptions (lemmas below state the precise bounds). This then implies that (6) holds.

We start with some basic facts (and notation) about Minimum Steiner trees (minST) of $S(\subset V)$ in $\mathcal{G}(n,p)$, with our parameters. We will refer to the vertices in $S$ as the terminals, and the rest of the vertices in a minST as the non-terminals. First, the minST must have all its leaves to be terminals. Further, since every two vertices in $G$ have a path of length two, we must have $\mathsf{st}(S)\leq 2|S|-1$ for all $S$. This helps us bound the number of tree structures the minST of $S$ can have. We define this formally.

Given $S\subset V$, a tree structure for $S$ is a tree $T$ along with a mapping $g:V(S)\rightarrow V(T)$ which is one-one (not necessarily onto). The vertices in $T$ without an inverse image in $S$ are called internal vertices and the rest are also called fixed vertices. A tree structure for $S$ is valid if it is possible to ‘fill in’ the internal vertices with distinct vertices from $V$ such that all the edges in the tree are also present in $G$. [The relation to Steiner trees is apparent – the internal vertices are the Steiner vertices]. Given an internal vertex in $T$, the vertices of $G$ which take that position in some valid ‘filling in’ are called the set of candidates for that position.

Before we get to the lemmas, we note that the number of tree structures for $S$ of size $\leq 2|S|$ is at most $(2|S|)^{2|S|}$ (this is just by a naïve bound using the number of trees). Let us now bound the number of $i\in V$ for which $\mathsf{st}(S\cup i)\leq\mathsf{st}(S)+1$.

Let $S\subset V$ and $T$ be a tree structure for a min Steiner tree of $S$ (so the leaves of $T$ are elements of $S$). Then the number of candidates for each of the positions in $T$ is at most $(\log n)^{2|S|}$.

The proof is by induction on the size of $S$. The base case $|S|=1$ is trivial. Assume the result for all tree structures of sets of size $\leq|S|-1$. Now consider $S$. We may assume that $T$ has at least one non-terminal, as otherwise there is nothing to prove.

First, note that there exists a vertex $u\in T$ which is adjacent to at most one non-leaf vertex in $T$. This is because deleting all the leaves in $T$ gives a tree (which is not empty as there is at least one non-terminal in $T$), and a leaf in this tree our required $u$. If $u$ is a terminal, we could remove the leaves attached to $u$ (thus obtaining a subset $S^{\prime}$ of the terminals), and the remaining tree structure would be a valid min Steiner tree for $S^{\prime}$. Further, the set of non-terminals is precisely the same, and thus the inductive hypothesis implies the claim for $S$. Thus suppose $u$ is a non-terminal.

If degree$(u)>2$, then there are at least two leaves attached to $u$, thus the number of candidates for $u$ is only $\log^{2}n$. Consider one candidate $x$ for $u$. Let $T^{\prime}$ be the tree obtained by removing all the leaves attached to $u$ (thus $u$ is now a leaf), and $S^{\prime}$ be $S\cup x$ minus the set of leaves attached to $u$. Now $T^{\prime}$ is a min Steiner tree structure for $S^{\prime}$ (otherwise we can obtain a smaller tree for $S$). Thus by the inductive hypothesis, the number of candidates for any internal vertex in $T^{\prime}$ is at most $(\log n)^{2|S|-2}$. Since there are only $\log^{2}n$ of the $x$’s, it follows that the total #(candidates) for an internal vertex is at most $(\log n)^{2|S|}$.

This completes the proof, by induction. ∎

Let $S\subset V$. There are at most $(2|S|\log n)^{2|S|}$ vertices $i$ such that $\mathsf{st}(S\cup i)=\mathsf{st}(S)$.

Each such $i$ must be the internal vertex of some min Steiner tree for $S$, and there are at most $(2|S|)^{2|S|}$ tree structures. Lemma 3.5 now implies the claim. ∎

Let $S\subset V$. There are at most $(4|S|\log n)^{4|S|}\times n^{1/2}$ vertices $i$ such that $\mathsf{st}(S\cup i)=\mathsf{st}(S)+1$.

Let $i$ be such a vertex. First, note that if there exists a min Steiner tree for $S\cup i$ with $i$ as a leaf, we are done. This is because removing $i$ gives a min Steiner tree for $S$, and thus $i$ is a neighbour of an internal vertex in a min Steiner tree for $S$. Thus by Corollary 3.6 there are only $(2|S|\log n)^{2|S|}\times(2n^{1/2}\log n)$ such $i$.

Thus suppose that the min Steiner tree for $S\cup i$ has $i$ as an internal vertex. We will prove the bound as follows: we consider a tree structure $T$ of size $\mathsf{st}(S)+1$ with leaves being terminals from $S$; then we show that the number of candidates for any fixed position in $T$ is at most $(2|S|\log n)^{2|S|}n^{1/2}$. This suffices, because the number of choices of tree structures adds an additional factor of $(2|S|)^{2|S|}$.

Let us consider a structure $T$ as above, and a position $u$. Since $u$ is not a leaf, it has degree at least $2$. Let the degree be $d$, and let $T_{1},\dots,T_{d}$ be the subtrees of $T$ formed by removing $u$ (see figure …). Now if for some $i$, $T_{i}$ is the min Steiner tree for the terminals in $T_{i}$, we are done, because then, each candidate for $u$ must be neighbour of an internal vertex in the tree, and by Corollary 3.6 there are only $\sqrt{n}\times(2|S|\log n)^{2|S|}$ candidates. Thus for each $i$, $T_{i}$ must have a strictly smaller tree $T_{i}^{\prime}$. Let the vertex in $T_{1}$ connected to $u$ be called $b_{1}$. Now construct a new tree as follows: leave $T_{1}$ intact, and replace $T_{2},\dots,T_{d}$ by $T_{2}^{\prime},\dots,T_{d}^{\prime}$; connect $b_{1}$ to $T_{2}^{\prime},\dots,T_{d}^{\prime}$ using paths of length $2$. The number of edges in the new tree is now at most $|T|-d-(d-1)+2(d-1)$. The first term is the original cost, followed by removal of $u$, followed by the decrease by using $T_{i}^{\prime}$ as opposed to $T_{i}$, followed by the cost of adding length-2 paths.

Thus the new tree has cost at most $|T|-1$, and thus it is optimal for $S$! Further, $u$ is adjacent to $b_{1}$ which is an internal vertex, and thus the number of candidates is bounded by the desired quantity. ∎

Consider the sum $\sum_{i\in V}x_{S\cup i}$. Corollary 3.6 implies that there are at most $(L\log n)^{L}$ terms which contribute a value $x_{S}/L$. Lemma 3.7 implies that there are at most $n^{1/2}\cdot(2L\log n)^{2L}$ terms which contribute a value $x_{S}/(n^{1/4}L)$. Thus if we pick $(2L\log n)^{2L}<n^{1/4}$, we have the bound that the sum is at most $n^{1/2}x_{S}$, as desired.

Thus we have verified each of the constraints (1)-(3). This completes the proof of Theorem 3.1.

4 Gaps for the mixed hierarchy (SA+).

Consider the relaxation $SA_{t}$ described in (1)-(2), along with the constraint: $Z=(x_{ij})_{1\leq i,j\leq n}\succeq 0$. The solution considered earlier (Equation (5)) turns out to also satisfy this PSD condition with high probability. The entries of $Z$ are

where $A$ is the adjacency matrix of $G$. Now $A$ is a $\mathcal{G}(n,p)$ matrix with $p=n^{-1/2}\log n$. Thus the least eigenvalue is at least $-2\sqrt{np(1-p)}$ with high probability (by the Semicircle law). This is at least $-4n^{1/4}(\log n)^{1/2}$. Thus we have $A+4n^{1/4}\sqrt{\log n}I\succeq 0$. Using the fact that $J\succeq 0$, we obtain that $Z\succeq 0$.

We conjecture that even $L\approx n^{\varepsilon}$ levels does not reduce the integrality gap substantially. We need a different approach (involving a better argument for bounding the number of trees) to extend the arguments above to this range of $L$.

Integrality Gap for the Lasserre hierarchy

In this section, we show a gap instance with arbitrary large constant ratio for linear-round Lasserre relaxation, and a gap instance with $n^{\varepsilon}$ ratio for $n^{1-O(\varepsilon)}$-round Lasserre relaxation (Theorem 4.7). We also aim at maximizing the ratio of a polynomial-round Lasserre gap instance, getting a ratio of $\Omega(n^{2/53-\varepsilon})$ (Theorem 4.8).

Our construction is based on a variant of Tulsiani’s gap instance for Max $K$-CSP [Tul09] – we extend the parameter range of Tulsiani’s instance. Then we convert the Max $K$-CSP instance to a constraint-variable graph and duplicate the variable vertices, which is our gap instance for Densest $k$-subgraph. Note that the gap for Max $K$-CSP problem is indeed a set of random instances. The vector solution from Lasserre gap for Max $K$-CSP will help us exhibit a good Lasserre vector solution for Densest $k$-subgraph. We finally use the structure of random instances of Max $K$-CSP to show the soundness holds with high probability.

Now, let us proceed to the first step, the gap instance for Max $K$-CSP.

We start by defining the Max $K$-CSP problem.

The following theorem is an extension of the main theorem in [Tul09], showing that polynomial-round Lasserre relaxation cannot refute random Max $K$-CSP with high probability.

$\langle{\bm{V}}_{(S_{1},\alpha_{1})},{\bm{V}}_{(S_{2},\alpha_{2})}\rangle\geq 0$ for all $S_{1},S_{2},\alpha_{1},\alpha_{2}$;

$\langle{\bm{V}}_{(S_{1},\alpha_{1})},{\bm{V}}_{(S_{2},\alpha_{2})}\rangle=0$ if $\alpha_{1}(S_{1}\cap S_{2})\neq\alpha_{2}(S_{1}\cap S_{2})$;

$\langle{\bm{V}}_{(S_{1},\alpha_{1})},{\bm{V}}_{(S_{2},\alpha_{2})}\rangle=\langle{\bm{V}}_{(S_{3},\alpha_{3})},{\bm{V}}_{(S_{4},\alpha_{4})}\rangle$ for all $S_{1}\cup S_{2}=S_{3}\cup S_{4}$ and $\alpha_{1}\circ\alpha_{2}=\alpha_{3}\circ\alpha_{4}$;

Recall that Tulsiani showed that, if the constraint-variable graph of a Max $K$-CSP$(C)$ instance has very high left-expansion, then the Lasserre SDP admits a perfect solution for it. Formally, the following lemma is (implicitly) shown in [Tul09].

Given a Max $K$-CSP$(C)$ instance, if every set of constraints of cardinality $s\leq r$ involves more than $(K-\delta)s$ variables (where $2\delta$ is the distance of the dual code of $C$), and if $4\delta\leq K$, then there is a perfect solution for the SDP relaxation obtained by $r/16$ rounds of the Lasserre hierarchy.

Hence, we only need to prove the following lemma which shows that the constraint-variable graph still has very high left-expansion, even when a constraint might involve superconstant many variables (i.e. the left degree might be superconstant).

Given $\beta,\eta,K$ as in Theorem 4.2, with probability $1-o(1)$, for all $2\leq s\leq\eta n$, every set of $s$ constraints involves more than $(K-\delta)s$ variables.

A similar lemma can be found in [Tul09] (Lemma A.1), which only deals with constant $K$. We need a more refined argument for superconstant $K$, which is in Section 4.4.

2 The Lasserre gap for Densest k𝑘k-subgraph.

The gap instance is reduced from the gap instance for Max $K$-CSP in Theorem 4.2. Let $C$ be the dual code of a $[K,K-t,2\delta]_{q}$ code as used in Theorem 4.2, where $K$ is the block length, $(K-t)$ is the dimension, and $2\delta\geq 3$ is the distance of the code. Such a code has size $|C|=q^{t}$, and is very sparse for small enough $t$. For $1000<q$ and $K>q^{2}$, we let $\beta=(40q^{t+2}\ln q)/K$, and do the following reduction.

Given a Max $K$-CSP$(C)$ instance $\Phi$ with $m=\beta n$ constraints and $n$ variables. Let $G_{\Phi}=(L_{\Phi},R_{\Phi},E_{\Phi})$ be the bipartite graph with $m|C|$ left vertices and $nq$ right vertices. For every constraint $C_{i}$ and every partial assignment to variables in the corresponding tuple $T_{i}$ which satisfies the constraint $C_{i}$, we introduce a left vertex. For every variable $x_{i}$ and its corresponding assignment, we introduce a right vertex. Formally,

We connect a left vertex $(C_{i},\alpha)$ and right vertex $(x_{j},\alpha^{\prime})$ when $x_{j}\in T_{i}$ and $\alpha^{\prime}$ is consistent with $\alpha$, i.e.

Now we define the final graph $G_{\Phi}^{\prime}=(L_{\Phi},R_{\Phi}^{\prime},E_{\Phi}^{\prime})$ in which we want to find a dense $k$-subgraph where $k=2m$. We take $\beta$ copies of the right vertices in $R_{\Phi}$ to get $R_{\Phi}^{\prime}$. To get $E_{\Phi}^{\prime}$, we connect a left vertex $u\in L_{\Phi}$ and a right vertex $v\in R_{\Phi}^{\prime}$ if $u$ is connected to $v$’s corresponding vertex in $R_{\Phi}$ in $E_{\Phi}$. The graph $G_{\Phi}^{\prime}$ has $N=m|C|+\beta nq=O(nq^{2t+2}\ln q/K)$ vertices.

In our analysis of the reduction, we need a $q$-ary linear code $\mathcal{C}$ that has a small constant distance (but no less than $3$), small block length (but more than $q$), and very high dimension. Thus, we instantiate the code $\mathcal{C}$ with Generalized BCH codes given by the following.

For every prime tower $q$, and integer $2\delta\geq 3$, there are $q$-ary linear codes of block length $K=q^{2}-1$, dimension $(K-4\delta+3)$, and distance at least $2\delta$.

We include a simple proof of Lemma 4.6 as follows.

We show the contrapositive statement : the only codeword of weight at most $D-1$ is $\bm{0}$. For every codeword of weight at most $D-1$, suppose the non-zero entries are in the set $\{c_{i_{1}},c_{i_{2}},c_{i_{3}},\cdots,c_{i_{D-1}}\}$, we have

Note that the coefficients form a Vandermonde matrix (which has full rank). Therefore we have $c_{i_{1}}=c_{i_{2}}=c_{i_{3}}=\cdots=c_{i_{D-1}}=0$, i.e. the codeword is $\bm{0}$.

3 Analysis.

We get a family of gap instances $G_{\Phi}^{\prime}$ parameterized by $q>1000$ and $2\delta\geq 3$ (using Lemma 4.6). We obtain our two main results of this section by picking appropriate parameters for code $C$ as follows. To get lasserre integrality gaps for $N^{1-O(\epsilon)}$ levels , we show the following by setting the distance $2\delta=3$.

For every $1000<q<N^{\epsilon}$ (where $\epsilon$ is an absolute small constant), there is a gap instance of ratio $\Omega(q)$ for $N/q^{O(1)}$-level Lasserre SDP. The same construction also works for the Min degree Lasserre SDP, when $q=\Omega(\log n)$ and $q<N^{\epsilon}$.

We now aim at getting a gap instance of ratio $N^{\epsilon}$ for polynomial-round Lasserre SDP, where $\epsilon$ is maximized. By setting $q=n^{\gamma}$ for some small constant $\gamma>0$, the distance $2\delta=4$, and optimizing the other parameters, we obtain the following (refer to section 4.3 for details)

For small enough $\kappa>0$, there is a gap instance of ratio $N^{2/53-O(\kappa)}$ for the $N^{\kappa}$-round Min degree Lasserre SDP.

The two theorems follow because of Theorem 4.2, Lemma 4.9, Lemma 4.11 (completeness) and Lemma 4.12 (soundness). In the completeness case, we will use our $r$-level Lasserre solution for Max $K$-CSP to show that the Lasserre SDP after $R=r/K$ levels of the hierarchy has value at least $\beta mK$. In the soundness case, we show that with probability $1-o(1)$, the graph $G_{\Phi}^{\prime}$ does not have any $2m$-subgraph of value more than $17/q$ times the SDP value (Lemma 4.12). Therefore, the graph $G_{\Phi}^{\prime}$ is a gap instance of ratio $\Omega(q)$ for $R$-round Lasserre SDP. We proceed by first proving these lemmas.

If the Max $K$-CSP$(C)$ instance $\Phi$ admits a perfect solution for $r$-round Lasserre SDP relaxation, then the $r/K$-round Lasserre SDP relaxation for the Densest $k$-subgraph instance $G_{\Phi}^{\prime}$ has a solution of value $\beta mK$.

For any set $S\subseteq L_{\Phi}\cup R_{\Phi}^{\prime}$, suppose the left vertices included in $S$ are

and the right vertices included in $S$ are

We have $|S^{\prime}|\leq Kr_{1}+r_{2}\leq r$. If all the partial assignments $\alpha_{i}$’s and $\alpha^{\prime}_{i}$’s are consistent to each other (i.e. there are not two of them assigning the same variable to different values), we can define

and let ${\bm{U}}_{S}={\bm{V}}_{(S^{\prime},\alpha)}$, or we let ${\bm{U}}_{S}=\bm{0}$.

For every $S\subseteq L_{\Phi}\cup R_{\Phi}^{\prime}$, we have $\langle{\bm{V}}_{(\emptyset,\emptyset)},{\bm{U}}_{S}\rangle=\left\lVert{\bm{U}}_{S}\right\rVert^{2}$.

If ${\bm{U}}_{S}={\bm{V}}_{(S^{\prime},\alpha)}$ for some $S^{\prime},\alpha$, we have $\langle{\bm{V}}_{(\emptyset,\emptyset)},{\bm{U}}_{S}\rangle=\langle{\bm{V}}_{(\emptyset,\emptyset)},{\bm{V}}_{(S^{\prime},\alpha)}\rangle=\left\lVert{\bm{V}}_{(S^{\prime},\alpha)}\right\rVert^{2}=\left\lVert{\bm{U}}_{S}\right\rVert^{2}$. If ${\bm{U}}_{S}=\bm{0}$, we have $\langle{\bm{V}}_{(\emptyset,\emptyset)},{\bm{U}}_{S}\rangle=\left\lVert{\bm{U}}_{S}\right\rVert^{2}=0$. ∎

We can check that all the Lasserre constraints are satisfied.

For two sets $S_{1},S_{2}$, either at least one of the vectors ${\bm{U}}_{S_{1}},{\bm{U}}_{S_{2}}$ is $\bm{0}$ (therefore their inner-product is ), or ${\bm{U}}_{S_{1}}={\bm{V}}_{S_{1}^{\prime},\alpha_{1}},{\bm{U}}_{S_{2}}={\bm{V}}_{S_{2}^{\prime},\alpha_{2}}$ for some $S_{1}^{\prime},S_{2}^{\prime},\alpha_{1},\alpha_{2}$ and $\langle{\bm{U}}_{S_{1}},{\bm{U}}_{S_{2}}\rangle=\langle{\bm{V}}_{S_{1}^{\prime},\alpha_{1}},{\bm{V}}_{S_{2}^{\prime},\alpha_{2}}\rangle\geq 0$.

For any $S_{1},S_{2},S_{3},S_{4}$ such that $S_{1}\cup S_{2}=S_{3}\cup S_{4}$, either the set of partial assignments in $S_{1}\cup S_{2}=S_{3}\cup S_{4}$ are consistent to each other, in which case we have ${\bm{U}}_{S_{1}\cup S_{2}}={\bm{U}}_{S_{3}\cup S_{4}}={\bm{V}}_{S,\alpha}$ where $S$ is the union of all the variables included in $S_{1}\cup S_{2}$ and $\alpha$ is the concatenation of the partial assignments in $S_{1}\cup S_{2}$; or we have ${\bm{U}}_{S_{1}\cup S_{2}}={\bm{U}}_{S_{3}\cup S_{4}}=\bm{0}$.

where the third last equality is because of Observation 4.3, and the second last equality is because of Observation 4.10.

Finally, we have $\left\lVert{\bm{U}}_{\emptyset}\right\rVert^{2}=\left\lVert{\bm{V}}_{(\emptyset,\emptyset)}\right\rVert^{2}=1$.

Now, we calculate the value of the solution

If we add the constraint (4), we can still get a good SDP solution for the Min degree Lasserre SDP with high probability, as long as $q$ is superconstant.

For $q=\Omega(\log n)$, with probability $1-o(1)$, this vector solution also satisfies the added constraint (4) with $d=\beta K/2$, i.e., for every set $S$, for each vertex $u$, we have

For each left vertex $(C_{i},\alpha)$, we have

For each right vertex $(x_{j},\alpha^{\prime})$, we have

where the last equality is because we know that ${\bm{U}}_{\{(C_{i},\alpha)\}}=\bm{0}$ when $C_{i}(\alpha)\neq 1$. By the property of Lasserre vectors, we know that for each $i\in[m]$,

For $q=\Omega(\log n)$, the expected number of constraints containing $x_{j}$ is $\beta K=\Omega((\log n)^{t+2})=\Omega(\log n)$, by our choice of $\beta$. Therefore, by Chernoff bound and union bound, with probability $1-o(1)$, for all $x_{j}$, there are at least $\beta K/2$ constraints containing $x_{j}$, and for every $S$, $x_{j}$ and $\alpha^{\prime}$, we have

Soundness.

Now, we show that random instances of Max $K$-CSP give rise to graphs $G^{\prime}_{\varphi}$ whose $2m$-sized subgraphs have density $O(\beta K/q)$. Note that the large alphabet size $q$ allows us to get a much larger gap than we would starting from random AND instances [Fei02]. This allows us some slack in the size of the subgraphs we need to argue about.

For $C$ the dual of a $[K,K-t,2\delta]_{q}$ code, we prove the following soundness lemma.

When $\beta\geq(40q^{t+2}\ln q)/K$, for a random Max $K$-CSP$(C)$ instance $\Phi$, with probability $1-o(1)$, any subgraph of $G_{\Phi}^{\prime}$ obtained by choosing $2m$ left vertices and $2m$ right vertices contains at most $17\beta mK/q$ edges, and therefore any $2m$-subgraph of $G_{\Phi}^{\prime}$ contains at most $17\beta mK/q$ edges.

Note that $G^{\prime}_{\varphi}$ was constructed by taking $\beta$ copies of the right bipartition and replicating the edges. To prove Lemma 4.12, we only need to prove the following lemma.

Suppose that $q>1000,K>q^{2}/2,t\leq 10$. When $\beta\geq(40q^{t+2}\ln q)/K$, for a random Max $K$-CSP$(C)$ instance $\Phi$, with probability $1-o(1)$, any subgraph of $G_{\Phi}$ obtained by choosing $2m$ left vertices and $2n$ right vertices contains at most $17mK/q$ edges.

We only need to prove once there is a $2m\times 2m$ subgraph of $G_{\Phi}^{\prime}$ with $t$ edges, there is a $2m\times 2n$ subgraph of $G_{\Phi}$ with at least $t/\beta$ edges. Fix $2m$ left vertices in $G_{\Phi}^{\prime}$, to maximize the number of edges in the subgraph, we need to select the $2m$ right vertices with most edges connected to the chosen $2m$ left vertices. Since any two right vertices $G_{\Phi}^{\prime}$ corresponding to the same right vertex in $G_{\Phi}$ have the same set of neighbors, there is an densest $2m\times 2m$ subgraph $H^{\prime}$ of $G_{\Phi}^{\prime}$ that, for any two such vertices, chooses either both or neither of them. Now we define an subgraph $H$ of $G_{\Phi}$ that contains the same $2m$ left vertices. It contains a right vertex if any copy of the vertex is contained in $H^{\prime}$. $H$ contains $2m/\beta=2n$ vertices, and it is easy to see that there are (at least) $t/\beta$ edges in $H$. ∎

We proceed by fixing a set of $2n$ vertices $R$ on the right. Lemma 4.13 follows from the following claim by a standard union bound over all possible choices of $R$.

Recall that $G_{\Phi}=(L_{\Phi},R_{\Phi},E_{\Phi})$. Suppose that $q>1000,K>q^{2}/2,t\leq 10$. Fix a subset $R\subseteq R_{\Phi}$ (note that $R_{\Phi}$ is the same for all the instances $\Phi$ of $n$ variables), $|R|=2n$, the probability (over choice of $\Phi$) that there does not exist a subset $L\subseteq L_{\Phi}$ of size $2m$ such that the number of edges in the induced subgraph by $L\cup R$ is more than $17mK/q$, is at least $1-\exp(-mK/(10q^{t+2}))$.

Since there are only ${qn\choose 2n}\leq\exp(2n(\ln q+1))$ choices of $R$, by a union bound, with probability at least

there is no $2m\times 2n$ subgraph of $G_{\Phi}$ containing more than $17mK/q$ edges. The probability becomes $1-o(1)$ when $\beta=(40q^{t+2}\ln q)/K$. ∎

(Proof of Claim 4.14) First, we show that with high probability, a constraint $C_{i}$ is “poorly satisfied”. That is, none of the left vertices corresponding to a constraint $C_{i}$ has more than $\Omega(K/q)$ neighbors in $R$ – this number is roughly $1/q$ times the corresponding value in completeness case. We prove this in the following two steps.

For a random $T$ with $|T|=K$, note that the expected degree $\mathop{\bf E\/}[\deg(T)]=2K$. Therefore, by Hoeffding’s inequalities for sampling without replacement (Theorem 1 and Theorem 4 in [Hoe62]), we have

Since there are $|C|=q^{t}\leq q^{10}$ codewords, by a union bound, for $K>q^{2}/2$ and $q>1000$, we have

Now, again, by standard Chernoff bound, we have

By the calculation above we know that with probability at least $1-\exp(-mK/(10q^{t+2}))$, there are at most $m/(q\cdot|C|)$ constraints that are not poorly satisfied.

For each left vertex $(C_{i},\alpha)\in L_{\Phi}$, if $C_{i}$ is poorly satisfied, we know there are at most $8K/q$ edges from $(C_{i},\alpha)$ to $R$. If $C_{i}$ is not poorly satisfied, there are at most $K$ edges to $R_{\Phi}$ – this upperbound also applies to $R$.

Therefore, with probability at least $1-\exp(-mK/(10q^{t+2}))$, any set of $2m$ left vertices has at most $2m\cdot 8K/q+m/(q\cdot|C|)\cdot|C|\cdot K\leq 17mK/q$ edges connected to $R$. ∎

We now complete the proofs of the main theorems in this section.

Proof of Theorem 4.7.

By combining Theorem 4.2, Lemma 4.9, Lemma 4.11 (completeness), and Lemma 4.12 (soundness) we see that with probability $1-o(1)$, the graph $G^{\prime}_{\Phi}$ provides a $\Omega(q)$ integrality for the number of levels $R$ given by

Recall that $K=q^{2}-1$. By setting $K=q^{2}-1$ and $2\delta=3$, we verify that the theorem holds. ∎

Proof of Theorem 4.8.

Let $q=n^{\gamma}$, since $N=O(nq^{2t+2}\ln q/K)=O(nq^{2t}\ln q)$, ratio of the gap due to Lemma 4.9 and Lemma 4.12 is

Note that when $2\delta\geq 3$ is fixed, $\epsilon$ is maximized when $\gamma$ is maximized.

The number of rounds (due to Theorem 4.2 and Lemma 4.9) is

For very small $\kappa>0$, to get a gap instance for $N^{\Omega(\kappa)}$-round Lasserre, we need

Let $\gamma=\frac{1-O(\kappa)}{10+6.5/(\delta-1)}$, we have

When $2\delta=4$, we get the maximized value $\epsilon=2/53-O(\kappa)$. ∎

4 Expansion for random Max K𝐾K-CSP instances.

In this section, we prove Lemma 4.5, restated as follows.

Lemma 4.5 (restated). Given $\beta,\eta,K$ as in Theorem 4.2, with probability $1-o(1)$, for all $2\leq s\leq\eta n$, every set of $s$ constraints involves more than $(K-\delta)s$ variables.

Fix $2\leq s\leq\eta n$, let us upperbound the probability that there is a set of $s$ constraints containing at most $(K-\delta)s$ variables. Since there are ${\beta n\choose s}$ such sets, the probability is at most

Fix a set $T$ of $i$ variables, let $p(s,i)$ be the number of $s$-tuples $(T_{1},T_{2},\cdots,T_{s})$ where for each $1\leq j\leq s$, $T_{j}$ is a set of $K$ variables, such that $\cup_{1\leq j\leq s}T_{j}=T$. We have

To upperbound $p(i,s)$, we view the way to enumerating valid $(T_{1},T_{2},\cdots,T_{s})$ as, to choose a multiset of $Ks$ variables (each one from $T$) so that each element in $T$ appears at least once in the multiset, then view each element in the multiset as a distinct element, and distribute these $Ks$ elements to $s$ sets, in a balanced way. Note that in this way, we are able to enumerate all the valid $s$-tuples (although some of them might be enumerated more than once). Since there are at most ${Ks-1\choose i-1}<{Ks\choose i}$ valid multisets, we have