Almost-Polynomial Ratio ETH-Hardness of Approximating Densest $k$-Subgraph

Introduction

In the Densest $k$-Subgraph (D$k$S) problem, we are given an undirected graph $G$ on $n$ vertices and a positive integer $k\leqslant n$. The goal is to find a set $S$ of $k$ vertices such that the induced subgraph on $S$ has maximum number of edges. Since the size of $S$ is fixed, the problem can be equivalently stated as finding a $k$-subgraph (i.e. subgraph on $k$ vertices) with maximum density where densityIt is worth noting that sometimes density is defined as $|E(S)|/|S|$. For D$k$S, both definitions of density result in the same objective since $|S|=k$ is fixed. However, our notion is more convenient to deal with as it always lies in $$. of the subgraph induced on$S$is$|E(S)|/\binom{|S|}{2}$and$E(S)$denotes the set of all edges among the vertices in$S$.

Densest $k$-Subgraph, a natural generalization of $k$-Clique [Kar72], was first formulated and studied by Kortsarz and Peleg [KP93] in the early 90s. Since then, it has been the subject of intense study in the context of approximation algorithm and hardness of approximation [FS97, SW98, FL01, FKP01, AHI02, Fei02, Kho06, GL09, RS10, BCC+10, AAM+11, BCV+12, Bar15, BKRW17]. Despite this, its approximability still remains wide open and is considered by some to be an important open question in approximation algorithms [BCC+10, BCV+12, BKRW17].

While the above algorithms demonstrate the main progresses of approximations of D$k$S in general case over the years, many special cases have also been studied. Most relevant to our work is the case where the optimal $k$-subgraph has high density, in which better approximations are known [FS97, ST08, MM15, Bar15]. The first and most representative algorithm of this kind is that of Feige and Seltser [FS97], which provides the following guarantee: when the input graph contains a $k$-clique, the algorithm can find an $(1-\varepsilon)$-dense $k$-subgraph in $n^{O(\log n/\varepsilon)}$ time. We will refer to this problem of finding densest $k$-subgraph when the input graph is promised to have a $k$-clique Densest $k$-Subgraph with perfect completeness.

Although many algorithms have been devised for D$k$S, relatively little is known regarding its hardness of approximation. While it is commonly believed that the problem is hard to approximate to within some polynomial ratio [AAM+11, BCV+12], not even a constant factor NP-hardness of approximation is known. To circumvent this, Feige [Fei02] came up with a hypothesis that a random 3SAT formula is hard to refute in polynomial time and proved that, assuming this hypothesis, D$k$S is hard to approximate to within some constant factor.

Alon et al. [AAM+11] later used a similar conjecture regarding random $k$-AND to rule out polynomial-time algorithms for D$k$S with any constant approximation ratio. Moreover, they proved hardnesses of approximation of D$k$S under the following Planted Clique Hypothesis [Jer92, Kuč95]: there is no polynomial-time algorithm that can distinguish between a typical Erdős–Rényi random graph $\mathcal{G}(n,1/2)$ and one in which a clique of size polynomial in $n$ (e.g. $n^{1/3}$) is planted. Assuming this hypothesis, Alon et al. proved that no polynomial-time algorithm approximates D$k$S to within any constant factor. They also showed that, when the hypothesis is strengthened to rule out not only polynomial-time but also super-polynomial time algorithms for the Planted Clique problem, their inapproximability guarantee for D$k$S can be improved. In particular, if no $n^{O(\sqrt{\log n})}$-time algorithm solves the Planted Clique problem, then $2^{O(\log^{2/3}n)}$-approximation for D$k$S cannot be achieved in polynomial time.

There are also several inapproximability results of D$k$S based on worst-case assumptions. Khot [Kho06] showed, assuming NP $\not\subseteq$ BPTIME($2^{n^{\varepsilon}}$) for some constant $\varepsilon>0$, that no polynomial-time algorithm can approximate D$k$S to within $(1+\delta)$ factor where $\delta>0$ is a constant depending only on $\varepsilon$; the proof is based on a construction of a “quasi-random” PCP, which is then used in place of a random 3SAT in a reduction similar to that from [Fei02].

While no inapproximability of D$k$S is known under the Unique Games Conjecture, Raghavendra and Steurer [RS10] showed that a strengthened version of it, in which the constraint graph is required to satisfy a “small-set expansion” property, implies that D$k$S is hard to approximate to within any constant ratio.

Since none of these inapproximability results achieve a polynomial ratio, there have been efforts to prove better lower bounds for more restricted classes of algorithms. For example, Bhaskara et al. [BCV+12] provided polynomial ratio lower bounds against strong SDP relaxations of D$k$S. Specifically, for the Sum-of-Squares hierarchy, they showed integrality gaps of $n^{2/53-\varepsilon}$ and $n^{\varepsilon}$ against $n^{\Omega(\varepsilon)}$ and $n^{1-O(\varepsilon)}$ levels of the hierarchy respectively. (See also [Man15, CMMV17] in which $2/53$ in the exponent was improved to $1/14$.) Unfortunately, it is unlikely that these lower bounds can be translated to inapproximability results and the question of whether any polynomial-time algorithm can achieve subpolynomial approximation ratio for D$k$S remains an intriguing open question.

In this work, we rule out, under the exponential time hypothesis (i.e. no subexponential time algorithm can solve 3SAT; see Hypothesis 4), polynomial-time approximation algorithms for D$k$S (even with perfect completeness) with slightly subpolynomial ratio:

There is a constant $c>0$ such that, assuming ETH, no polynomial-time algorithm can, given a graph $G$ on $n$ vertices and a positive integer $k\leqslant n$, distinguish between the following two cases:

There exist $k$ vertices of $G$ that induce a $k$-clique.

Every $k$-subgraph of $G$ has density at most $n^{-1/(\log\log n)^{c}}$.

If we assume a stronger assumption that it takes exponential time to even distinguish between a satisfiable 3SAT formula and one which is only $(1-\varepsilon)$-satisfiable for some constant $\varepsilon>0$ (aka Gap-ETH; see Hypothesis 5), the ratio can be improved to $n^{f(n)}$ for any Recall that $f\in o(1)$ if and only if $\lim_{n\to\infty}f(n)=0$. $f\in o(1)$:

For every function $f\in o(1)$, assuming Gap-ETH, no polynomial-time algorithm can, given a graph $G$ on $n$ vertices and a positive integer $k\leqslant n$, distinguish between the following two cases:

There exist $k$ vertices of $G$ that induce a $k$-clique.

Every $k$-subgraph of $G$ has density at most $n^{-f(n)}$.

We remark that, for D$k$S with perfect completeness, the aforementioned Feige-Seltser algorithm achievesThis guarantee was not stated explicitly in [FS97] but it can be easily achieved by changing the degree threshold in their algorithm DenseSubgraph from $(1-\varepsilon)n$ to $n^{\varepsilon}$. an $n^{\varepsilon}$-approximation in time $n^{O(1/\varepsilon)}$ for every $\varepsilon>0$ [FS97]. Hence, the ratios in our theorems cannot be improved to some fixed polynomial and the ratio in Theorem 2 is tight in this sense.

Comparison to Previous Results. In terms of inapproximability ratios, the ratios ruled out in this work are almost polynomial and provides a vast improvement over previous results. Prior to our result, the best known ratio ruled out under any worst case assumption is only any constant [RS10] and the best ratio ruled out under any average case assumption is only $2^{O(\log^{2/3}n)}$ [AAM+11]. In addition, our results also have perfect completeness, which was only achieved in [BKRW17] under ETH and in [AAM+11] under the Planted Clique Hypothesis but not in [Kho06, Fei02, RS10].

Implications of Our Results. One of the reasons that D$k$S has received significant attention in the approximation algorithm community is due to its connections to many other problems. Most relevant to our work are the problems to which there are reductions from D$k$S that preserve approximation ratios to within some polynomialThese are problems whose $O(\rho)$-approximation gives an $O(\rho^{c})$-approximation for D$k$S for some constant $c$.. These problems include Densest At-Most-$k$-Subgraph [AC09], Smallest $m$-Edge Subgraph [CDK12], Steiner $k$-Forest [HJ06] and Quadratic Knapsack [Pis07]. For brevity, we do not define these problems here. We refer interested readers to cited sources for their definitions and reductions from D$k$S to respective problems. We also note that this list is by no means exhaustive and there are indeed numerous other problems with similar known connections to D$k$S (see e.g. [HJL+06, KS07, KMNT11, CHK11, HIM11, LNV14, CLLR15, CL15, CZ15, SFL15, TV15, CDK+16, CMVZ15, Lee16]). Our results also imply hardness of approximation results with similar ratios to D$k$S for such problems:

For some constant $c>0$, assuming ETH, there is no polynomial-time $n^{1/(\log\log n)^{c}}$-approximation algorithm for Densest At-Most-$k$-Subgraph, Smallest $m$-Edge Subgraph, Steiner $k$-Forest, Quadratic Knapsack. Moreover, for any function $f\in o(1)$, there is no polynomial-time $n^{f(n)}$-approximation algorithm for any of these problems, unless Gap-ETH is false.

Preliminaries and Notations

We use $\exp(x)$ and $\log(x)$ to denote $e^{x}$ and $\log_{2}(x)$ respectively. $\operatorname*{polylog}n$ is used as a shorthand for $O(\log^{c}n)$ for some constant $c$. For any set $S$, $\mathscr{P}(S):=\{T\mid T\subseteq S\}$ denotes the power set of $S$. For any non-negative integer $t\leqslant|S|$, we use $\binom{S}{t}:=\{T\in\mathscr{P}(S)\mid|T|=t\}$ to denote the collection of all subsets of $S$ of size $t$.

One of our results is based on the exponential time hypothesis (ETH), a conjecture proposed by Impagliazzo and Paturi [IP01] which asserts that 3SAT cannot be solved in subexponential time:

No $2^{o(m)}$-time algorithm can decide whether any 3SAT formula with $m$ clausesIn its original form, the running time lower bound is exponential in the number of variables not the number of clauses; however, thanks to the sparsification lemma of Impagliazzo et al. [IPZ01], both versions are equivalent. is satisfiable.

Another hypothesis used in this work is Gap-ETH, a strengthened version of the ETH, which essentially states that even approximating 3SAT to some constant ratio takes exponential time:

There exists a constant $\varepsilon>0$ such that no $2^{o(m)}$-time algorithm can, given a 3SAT formula $\phi$ with $m$ clausesAs noted by Dinur [Din16], a subsampling argument can be used to make the number of clauses linear in the number of variables, meaning that the conjecture remains the same even when $m$ denotes the number of variables., distinguish between the case where $\phi$ is satisfiable and the case where $\operatorname*{val}(\phi)\leqslant 1-\varepsilon$. Here $\operatorname*{val}(\phi)$ denote the maximum fraction of clauses of $\phi$ satisfied by any assignment.

2 Nearly-Linear Size PCPs and Subexponential Time Reductions

The celebrated PCP Theorem [AS98, ALM+98], which lies at the heart of virtually all known NP-hardness of approximation results, can be viewed as a polynomial-time reduction from 3SAT to a gap version of 3SAT, as stated below. While this perspective is a rather narrow viewpoint of the theorem that leaves out the fascinating relations between parameters of PCPs, it will be the most convenient for our purpose.

For some constant $\varepsilon>0$, there exists a polynomial-time reduction that takes a 3SAT formula $\varphi$ and produces a 3SAT formula $\phi$ such that

(Completeness) if $\varphi$ is satisfiable, then $\phi$ is satisfiable, and,

(Soundness) if $\varphi$ is unsatisfiable, then $\operatorname*{val}(\phi)\leqslant 1-\varepsilon$.

Following the first proofs of the PCP Theorem, considerable efforts have been made to improve the trade-offs between the parameters in the theorem. One such direction is to try to reduce the size of the PCP, which, in the above formulation, translates to reducing the size of $\phi$ relative to $\varphi$. On this front, it is known that the size of $\phi$ can be made nearly-linear in the size of $\varphi$ [Din07, MR08, BSS08]. For our purpose, we will use Dinur’s PCP Theorem [Din07], which has a blow-up of only polylogarithmic in the size of $\phi$:

For some constant $\varepsilon,d>0$, there exists a polynomial-time reduction that takes a 3SAT formula $\varphi$ with $m$ clauses and produces another 3SAT formula $\phi$ with $m^{\prime}=O(m\operatorname*{polylog}m)$ clauses such that

(Completeness) if $\varphi$ is satisfiable, then $\phi$ is satisfiable, and,

(Soundness) if $\varphi$ is unsatisfiable, then $\operatorname*{val}(\phi)\leqslant 1-\varepsilon$, and,

(Bounded Degree) each variable of $\phi$ appears in $\leqslant d$ clauses.

Note that Dinur’s PCP, combined with ETH, implies a lower bound of $2^{\Omega(m/\operatorname*{polylog}m)}$ on the running time of algorithms that solve the gap version of 3SAT, which is only a factor of $O(\operatorname*{polylog}m)$ in the exponent off from Gap-ETH. Putting it differently, Gap-ETH is closely related to the question of whether a linear size PCP, one where the size blow-up is only constant instead of polylogarithmic, exists; its existence would mean that Gap-ETH is implied by ETH.

The Reduction and Proofs of The Main Theorems

To bound $|\mathcal{K}_{t,t}|$, we will prove the following bound on $|\mathcal{K}_{t,t}(A,B)|$.

Before we prove the above lemma, let us see how Lemma 9 and Lemma 10 imply Theorem 8.

First, notice that if $(x,b)$ appears in $A$ and $(x,\neg b)$ appears in $B$ for some variable $x$ and bit $b$, then $\mathcal{K}_{t,t}(A,B)=\emptyset$; this is because, for any $L$ with $\mathcal{A}(L)=A$ and $R$ with $\mathcal{A}(R)=B$, there exist $u\in L$ and $v\in R$ that contain $(x,b)$ and $(x,\neg b)$ respectively, meaning that there is no edge between $u$ and $v$ and, thus, $(L,R)\notin\mathcal{K}_{t,t}(A,B)$. Hence, from now on, we can assume that, if $(x,b)$ appears in one of $A,B$, then the other does not contain $(x,\neg b)$. Observe that this implies that, for each variable $x$, its assignments can appear in $A$ and $B$ at most two timesThis is where we use the fact that the variables are boolean. For non-boolean CSPs, each variable $x$ can appear more than two times in one of $A$ or $B$ alone, which can indeed be problematic (see Appendix A). in total. This in turn implies that $|A|+|B|\leqslant 2n$.

$x$ is terrible iff its assignments appear at most once in total in $A$ and $B$ (i.e. $|\{(x,0),(x,1)\}\cap A|+|\{(x,0),(x,1)\}\cap B|\leqslant 1$).

$x$ is good iff, for some $b\in\{0,1\}$, $(x,b)\in A\cap B$. Note that this implies that $(x,\neg b)\notin A\cup B$.

$x$ is bad iff either $\{(x,0),(x,1)\}\subseteq A$ or $\{(x,0),(x,1)\}\subseteq B$.

The next and last step of the proof is where birthday-type paradoxes come in. Before we continue, let us briefly demonstrate the ideas behind this step by considering the following extreme cases:

If all variables are terrible, then $|A|+|B|\leqslant n$ and (3) can be immediately tightened.

To turn this intuition into a bound on $|\mathcal{K}_{t,t}(A,B)|$, we need the following inequality. Its proof is straightforward and is deferred to Subsection 3.1.

Let $U$ be any set and $P\subseteq\binom{U}{2}$ be any set of pairs of elements of $U$ such that each element of $U$ appears in at most $q$ pairs. For any positive integer $2\leqslant r\leqslant|U|$, the probability that a random element of $\binom{U}{r}$ does not contain both elements of any pair in $P$ is at most $\exp\left(-\frac{|P|r^{2}}{4q|U|^{2}}\right)$.

We are now ready to formalize the above intuition and finish the proof of Lemma 10. For the sake of convenience, denote the sets of good, bad and terrible variables by $X_{g},X_{b}$ and $X_{t}$ respectively. Moreover, let $\beta:=\varepsilon/(100d)$ and pick $\lambda=\min\{-\log(1-\beta/2),\beta/64,\varepsilon/(384d)\}$. To refine the bound on the size of $\mathcal{K}_{t,t}(A,B)$, consider the following three cases:

$|X_{b}|\geqslant\beta n$. Since each $x\in X_{b}$ appears either in $A$ or $B$, one of $A$ and $B$ must contain assignments to at least $(\beta/2)n$ variables in $X_{b}$. Assume w.l.o.g. that $A$ satisfies this property. Let $X_{b}^{L}$ be the set of all $x\in X_{b}$ whose assignments appear in $A$. Note that $|X_{b}^{L}|\geqslant(\beta/2)n$.

$|X_{t}|<\beta n$ and $|X_{b}|<\beta n$. In this case, $|X_{g}|>(1-2\beta)n$. Let $S$ denote the set of clauses whose variables all lie in $X_{g}$. Since each variable appears in at most $d$ clauses, $|S|>m-(2\beta n)d\geqslant(1-\varepsilon/2)m$ where the second inequality comes from our choice of $\beta$ and from $m\geqslant n/3$.

Consider the partial assignment $f:X_{g}\rightarrow\{0,1\}$ induced by $A$ and $B$, i.e., $f(x)=b$ iff $(x,b)\in A,B$. Since $\operatorname*{val}(\phi)\leqslant 1-\varepsilon$, the number of clauses in $S$ satisfied by $f$ is at most $(1-\varepsilon)m$. Hence, at least $\varepsilon m/2$ clauses in $S$ are unsatisfied by $f$. Denote the set of such clauses by $S_{\text{UNSAT}}$.

We first construct $P^{\prime}\subseteq P$ such that each element of $U$ appears in at most one pair in $P^{\prime}$ as follows. Start out by marking every pair in $P$ as active and, as long as there are active pairs left, include one in $P^{\prime}$ and mark every pair that shares an element of $U$ with this pair as inactive. Since each element of $U$ appears in at most $q$ pairs in $P$, we mark at most $2q$ pairs as inactive per each inclusion. This implies that $|P^{\prime}|\geqslant|P|/(2q)$.

Suppose that $P^{\prime}=\{\{a_{1},b_{1}\},\dots,\{a_{|P^{\prime}|},b_{|P^{\prime}|}\}\}$ where $a_{1},b_{1},\dots,a_{|P^{\prime}|},b_{|P^{\prime}|}$ are distinct elements of $U$. Let $u$ be a random element of $\binom{U}{r}$. For each $i=1,\dots,|P^{\prime}|$, we have

If $u$ does not contain both elements of any pairs in $P$, it does not contain both elements of any pairs in $P^{\prime}$. The probability of the latter can be written as

In addition, since $a_{1},b_{1},\dots,a_{|P^{\prime}|},b_{|P^{\prime}|}$ are distinct, it is not hard to see that $\Pr\left[\{a_{i},b_{i}\}\not\subseteq u\middle|\>\bigwedge_{j=1}^{i-1}\{a_{j},b_{j}\}\not\subseteq u\right]\leqslant\Pr[\{a_{i},b_{i}\}\not\subseteq u]$. Hence, we have

completing the proof of Proposition 11. $\square$

2 Proofs of Inapproximability Results of Dk𝑘kS

The proof of Theorem 2 is even simpler since, under Gap-ETH, we have the gap version of 3SAT to begin with. Hence, we can directly apply Theorem 8 without going through Dinur’s PCP:

Conclusion and Open Questions

In this work, we provide a subexponential time reduction from the gap version of 3SAT to D$k$S and prove that it establishes an almost-polynomial ratio hardness of approximation of the latter under ETH and Gap-ETH. Even with our results, however, approximability of D$k$S still remains wide open. Namely, it is still not known whether it is NP-hard to approximate D$k$S to within some constant factor, and, no polynomial ratio hardness of approximation is yet known.

Although our results appear to almost resolve the second question, it still seems out of reach with our current knowledge of hardness of approximation. In particular, to achieve a polynomial ratio hardness for D$k$S, it is plausible that one has to prove a long-standing conjecture called the sliding scale conjecture (SSC) [BGLR93]. In short, SSC essentially states that Label Cover, a problem used as starting points of almost all NP-hardness of approximation results, is NP-hard to approximate to within some polynomial ratio. Note here that polynomial ratio hardness for Label Cover is not even known under stronger assumptions such as ETH or Gap-ETH; we refer the readers to [Din16] for more detailed discussions on the topic.

Apart from the approximability of D$k$S, our results also prompt the following natural question: since previous techniques, such as Feige’s Random 3SAT Hypothesis [Fei02], Khot’s Quasi-Random PCP [Kho06], Unique Games with Small Set Expansion Conjecture [RS10] and the Planted Clique Hypothesis [Jer92, Kuč95], that were successful in showing inapproximability of D$k$S also gave rise to hardnesses of approximation of many problems that are not known to be APX-hard including Sparsest Cut, Min Bisection, Balanced Separator, Minimum Linear Arrangement and 2-Catalog Segmentation [AMS07, Sak10, RST12], is it possible to modify our construction to prove inapproximability for these problems as well? An evidence suggesting that this may be possible is the case of $\varepsilon$-approximate Nash Equilibrium with $\varepsilon$-optimal welfare, which was first proved to be hard under the Planted Clique Hypothesis by Hazan and Krauthgamer [HK11] before Braverman, Ko and Weinstein proved that the problem was also hard under ETH [BKW15].

I am truly grateful to Aviad Rubinstein, Prasad Raghavendra and Luca Trevisan for invaluable discussions throughout various stages of this work. Without their comments, suggestions and support, this work would not have been possible. Furthermore, I thank Daniel Reichman and Igor Shinkar for stimulating dicussions on a related problem which inspire part of the proof presented here. I also thank Igor for pointing me to [Alo02]. Finally, I thank anonymous reviewers for their useful comments on an earlier draft of this work.

References

Appendix A A Counterexample to Obtaining a Subconstant Soundness from Non-Boolean CSPs

Finally, note that there are several ways to define constraints within $X_{1}$ and $X_{2}$ so that $\operatorname*{val}(\phi)$ is bounded away from one. For instance, we can make each side a random 2-XOR formula, which results in $\operatorname*{val}(\phi)\leqslant 1/2+O(1/d)$. Thus, if we start from a non-boolean CSP, the largest gap we can hope to get is only two.

Note that the instance above is rather extreme as it consists of two disconnected components. Hence, it is still possible that, if the starting CSP has more specific properties (e.g. expanding constraint graph), then one can arrive at a gap of more than two.