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

Abstract

In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that contains maximum number of edges. Even though the state-of-the-art algorithm for the problem achieves only $O(n^{1/4+\epsilon })$ approximation ratio (Bhaskara et al., 2010), previous attempts at proving hardness of approximation, including those under average case assumptions, fail to achieve a polynomial ratio; the best ratios ruled out under any worst case assumption and any average case assumption are only any constant (Raghavendra and Steurer, 2010) and $2^{\Omega ({\log }^{2/3}n)}$ (Alon et al., 2011) respectively. In this work, we propose the Almost-Exponential Time Hypothesis (Almost-ETH), which postulates that no algorithm can solve 3SAT on $n$ variables in $O(2^{n^{1-\gamma }})$ time for any constant $\gamma >0$. Assuming Almost-ETH, we show that, for any constant $\epsilon >0$, there is no polynomial-time algorithm that approximates {\sc D$k$S} to within $2^{(\log n{)}^{1-\epsilon }}$ factor of the optimum. In addition, our result has perfect completeness, meaning that, assuming Almost-ETH, no polynomial-time algorithm can even distinguish between the case in which $G$ contains a $k$-clique and the case in which every induced $k$-subgraph of $G$ has density at most $2^{-(\log n{)}^{1-\epsilon }}$.

arXiv commentIn the earlier versions of this work, the hardness results are stated under the ETH and Gap-ETH assumptions, which are now known to be false. The revision instead reframes the hardness under a weaker "Almost-ETH", which remains a plausible assumption. (The reduction, completeness and soundness proofs remain exactly the same as before.)