The Strongish Planted Clique Hypothesis and Its Consequences

In analogy to the Exponential Time Hypothesis for 3-SAT, we propose the following hypothesis, which postulates that the state-of-the-art algorithms for the Planted Clique Problem are optimal up to a constant factor in the exponent. A Strong Planted Clique Hypothesis, in analogy with SETH, would specify a precise constant in the exponent—our hypothesis is merely Strong-ish. We let $\mathcal{G}(n,p)$ denote the Erdős-Rényi distribution with parameter $p$, and $\mathcal{G}(n,p,\kappa)$ denote the Erdős-Rényi distribution with a planted $\kappa$-clique.

In addition to the lack of algorithmic progress toward refuting this hypothesis, we note that $n^{\Theta(\log(n))}$ is in fact provably optimal for the Sum-of-Squares hierarchy [BHK⁺19], which captures the state-of-the-art algorithmic techniques for a number of average-case problems. It is also known to be tight for statistical algorithms [FGR⁺17, BBH⁺20].

Our main technical contributions are in exploring the implications of our new SPCH in parameterized complexity. We prove two types of hardness results: hardness of approximation, and hardness of (exact) graph pattern detection. Due to the rich literature for each problem we consider, we will only mention the most relevant results here and defer a more comprehensive discussion to Section 1.4.

The starting point for all of our reductions is a randomized graph product: starting with an instance $G$ of the planted clique problem on $n$ vertices and any integers $\ell\leq n$ and $N$, we produce a graph $G^{\prime}$ by taking its vertices to be $N$ randomly sampled subsets $S_{1},\ldots,S_{N}$ of $\ell$ vertices each, and we add an edge on $S_{i},S_{j}$ if and only if their union induces a clique in $G$.

The randomized graph product [BS89] (and its derandomized variant [AFWZ95]) has a long history in proving hardness of approximating Maximum Clique. While not stated explicitly, it was also used to prove parameterized inapproximability of Densest $k$-Subgraph in [CCK⁺17]. As we will explain in more detail below, the main difference between our proof and previous works lie in the soundness, where we appeal to the fact that $G\sim\mathcal{G}(n,1/2)$ to achieve tighter bounds.

Since we would like to prove hardness of approximating Densest $k$-Subgraph in the perfect completeness case, our goal is to show (for appropriately chosen values of $N,\ell$) that

• •

  (Completeness) if $G$ contains a large clique, then with high probability so does $G^{\prime}$, and,

• •

  (Soundness) if $G$ is random, then $G^{\prime}$ does not have small dense subgraphs (with high probability).

For the completeness, if the starting graph $G$ has a $\kappa$-clique, then the set of $S_{i}$ that fall entirely within the $\kappa$-clique will form a clique in $G^{\prime}$ (the expected size is $(\frac{\kappa}{n})^{\ell}\cdot N$). This part of the proof is exactly the same as that in the aforementioned previous works.

To prove soundness, we calculate the probability that a specific $\gamma k$-dense $k$-subgraph appears in $G^{\prime}$, then take a union bound over all $\leq\binom{N}{k}\cdot 2^{\binom{k}{2}}$ possible such subgraphs. Our simple argument hinges on showing that a $k$-subgraph with $\gamma k^{2}$ edges in $G^{\prime}$ induces (with high probability) at least $\Omega(\gamma k^{2}\ell^{2})$ edges in $G$, and since any such set of edges appears in $G$ with probability at most $2^{-\Omega(\gamma k^{2}\ell^{2})}$, by choosing $\ell$ sufficiently large we can beat this union bound. To argue that small subgraphs with $m$ edges in $G^{\prime}$ induce small subgraphs with $\Omega(m\ell^{2})$ edges in $G$, we use that the randomly chosen $S_{i}$ (for an appropriate choice of $N\ll n^{\ell}$ and $k_{*}$ sufficiently small) form a disperser: the union of any $t\leq k_{*}$ of the $S_{i}$ contains $\Omega(t\ell)$ vertices of $G$ with high probability.⁴⁴4The fact that the randomized graph product yields a disperser has been used in previous works as well, see e.g. [BS89, Zuc96, CCK⁺17]. This implies that for $k\leq k_{*}$, each $k$-subgraph of $G^{\prime}$ corresponds to a union of $k$ pairwise mostly-non-overlapping subsets of $\ell$ vertices. Now, since each edge between mostly non-overlapping sets in $G^{\prime}$ corresponds to a $\Omega(\ell)$-clique in $G$, this in turn can be used to show that any $k$-subgraph of $G^{\prime}$ with density $\gamma k$ corresponds to a subgraph of $G$ with $\Omega(\gamma k^{2}\ell^{2})$ edges. In this way we rule out the existence of $\gamma k$-dense $k$-subgraphs in $G^{\prime}$ (with high probability).

By carefully choosing the parameters $N$, $\ell$, $\gamma$, to control the completeness, soundness, and reduction size, we get a fine-grained reduction from Planted $\kappa$-Clique to Densest $k$-Subgraph. Our results for other problems are obtained via direct reductions from the Densest $k$-Subgraph problem.

We end by stressing that our new soundness proof gives a strong quantitative improvement over prior results, which is what enables us to achieve $k^{\Omega(1)}$ inapproximability. Specifically, the previous soundness proof from [CCK⁺17]—in turn adapted from [Man17a]—relies on showing that the graph is $t$-biclique-free for some $t\in\mathbb{N}$; they then apply the so-called Kovari-Sos-Turan theorem [KST54] to deduce that any $k$-subgraph contains at most $O(k^{2-1/t})$ edges. Notice that this gap is only $O(k^{1/t})$, and $t$ cannot be a constant as otherwise the completeness and soundness case can be distinguished in time $n^{O(t)}=\poly(n)$. As a result, their technique cannot yield an $k^{\Omega(1)}$-factor inapproximability for Densest $k$-Subgraph. Similarly, the techniques from [CCK⁺17] cannot give a running time lower bound of the form $n^{\omega(\log k)}$ for $O(1)$-approximation of Densest $k$-Subgraph. The reason is that, to get a constant gap bounded from one, they need to select $t=O(\log k)$. Once again, this is in contrast to our technique which yields a tight running time lower bound of $n^{\Omega(k)}$ in this setting, although our proof requires a different starting hardness result (from SPCH).

In this work, we have proposed the Strongish Planted Clique Hypothesis, and used it prove several tight hardness of approximation or running time lower bound results. One direction for future investigation is to use SPCH to derive other interesting lower bounds.

Another intriguing question directly related to our hardness of approximation results is whether we can strengthen the inapproximability factors from $k^{\Omega(1)}$ to $n^{\Omega(1)}$. Whether it is hard to approximate Densest $k$-Subgraph to within a $n^{\Omega(1)}$ factor is a well-known open problem and is related to some other conjectures, such as the Sliding-Scaling Conjecture [BGLR93]⁵⁵5Specifically, from a reduction of [CHK11], $n^{\Omega(1)}$-factor hardness of approximation of Densest $k$-Subgraph also implies that of the Label Cover problem.. As such, it would be interesting if one can prove this hardness under some plausible assumption. We remark that an attempt has been made in this direction, using the so-called “Log-Density Threshold” approach [BCC⁺10], which posits a heuristic for predicting which average-case Densest-$k$-Subgraph problems are hard.

The approach has also been applied to other related questions [CDK12, CDM17a, CMMV17]. Nonetheless, there is still little evidence that these average-case DkS problems are indeed hard; not even lower bounds against strong SDP relaxations are known, although there are some matching lower bounds against LP hierarchies [BCV⁺12, CM18].

Finally, it is of course interesting to either refute or find more evidence supporting the Strongish Planted Clique Hypothesis. As stated earlier, the current best supporting evidence is the Sum-of-Squares lower bound from [BHK⁺19]. Can such a lower bound be extended to, e.g., rule out any semi-definite programs of size $n^{o(\log n)}$ (à la [LRS15] for CSPs)?

Historically, postulating hardness for average-case problems has been helpful in illuminating the landscape for hardness of approximation, beginning with Feige’s seminal random-$3$-SAT hypothesis [Fei02] and its numerous consequences (e.g. [DS16]). See also [Dan16, Ale11, ABW10, BKS13].

As discussed briefly above, the Planted Clique Hypothesis (PCH), which states that there is no polynomial-time algorithm for planted clique, has many known consequences for hardness of approximation. We draw attention in particular to the work of [AAM⁺11], which also obtains hardness of approximation results based on PCH. But even assuming the SPCH, their results can only rule out $n^{\polylog(\kappa)}$-time algorithms for $2^{\log(\kappa)^{2/3}}$-approximating densest-$\kappa$-subgraph for $\kappa=n^{\Omega(1)}$. Their reduction also uses a graph product, but the set of vertices of their new graph $G^{\prime}$ contains all $\ell$-size subsets of vertices of $G$. In contrast, we employ the randomized graph product, where we only randomly pick some $\ell$-size subsets—this allows us to better control the instance size blowup, which turns out to be crucial for obtaining our tight inapproximability and running time results.

Below we discuss in more detail the previous works for each of the problems studied here.

For a natural number $n\in\mathbb{N}$, we use $[n]$ to denote the set of integers up to $n$, $[n]=\{1,\ldots,n\}$. We will use the abbreviation “w.h.p.” to mean “with high probability.”

For an undirected graph $G=(V,E)$, we use $\deg_{G}(v)$ to denote the degree of a vertex $v\in V$, and $\operatorname{min-deg}(G)$ to denote $\min_{v\in V(G)}\deg_{G}(v)$. For a subset $S\subseteq V$, we use $G[S]=(V,E[S])$ to denote the induced subgraph of $G$ on subset $S$.

The density of $G$, denoted by $\operatorname{den}(G)$, is defined as $|E|/|V|$. We also use $\operatorname{den}_{\leq k}(G)$ to denote $\max_{S\subseteq V,|S|\leq k}\operatorname{den}(G[S])$, the maximum density of subgraphs of $G$ of at most $k$ vertices.

We first prove that applying the randomized graph product to a graph with a large clique results in a graph with a large clique.

We now prove that if we apply the randomized graph product to a graph drawn from $G(n,\frac{1}{2})$, with high probability the resulting graph has no small subgraphs which are too dense.

We will use the following observation that allows us to translate a graph with large density to a (sub)graph with large minimum degree. This observation is folklore and appears implicitly e.g. in [Cha00]. Nonetheless, we provide the proof in Appendix A for completeness.

Another auxiliary lemma that is useful for us is that for any subset $M\subseteq[N]$ not too large, the size of the union $\left|\cup_{j\in M}S_{j}\right|$ is not too small relative to $|M|\cdot\ell$. This lemma is also standard and has been used in prior works (e.g. [BS89, Zuc96, CCK⁺17]). Once again, we provide its proof in Appendix A for completeness.

With the above observation and lemma ready, we can now prove the soundness guarantee.

We start with the $n^{\Omega(k)}$ running time lower bound for $O(1)$-approximating Densest $k$-Subgraph, from which the remaining results easily follow. We remark that this running time lower bound improves upon that of $n^{\Omega(\log k)}$, which is implicit in [CCK⁺17].

We will prove Theorem 8 by simply selecting an appropriate setting of parameters for the randomized graph product. Specifically, we will let $\ell=O(C\log n/k)$ and $N=n^{O(\ell)}=n^{o(\log n)}$; the generic soundness lemma (Lemma 5) then implies that the density of any $k$-subgraph in the soundness case is at most $O(k/C)$ which yields the desired $C$ inapproximability factor.

Recall that a $k$-biclique, denoted by $K_{k,k}$, is a complete bipartite graph where each side has exactly $k$ vertices. In the $k$-Biclique problem, we are given an undirected graph $G$ and a positive integer $k$. Further, we are promised that $G$ contains a $K_{k,k}$ as a subgraph. Our goal is to output a balanced biclique in $G$ of size as large as possible. (Note that we say that an algorithm achieves $\alpha$-approximation if the output biclique has size at least $k/\alpha$.)

We prove the following tight running time lower bound for $O(1)$-approximation of $k$-Biclique:

Theorem 8 also yields the following corollary for the running time of pattern detection:

We start with the $o(k)$-factor hardness of Densest $k$-Subgraph, from which our other results follow.

The proof of Theorem 2 is once again via selecting an appropriate setting of parameters for the randomized graph product. Specifically, we will select $\ell=O((\log n)\cdot g(k)/k)$ where $g(k)=o(k)$ is the assumed approximation ratio and $N=n^{O(\ell)}=n^{o(\log n)}$; the generic soundness lemma (Lemma 5) then implies that the density of any $k$-vertex subgraph in the soundness case is at most $k/g(k)$ as desired. The arguments are formalized below.