ETH-hardness of Approximating Densest k-Subgraph

by Pasin Manurangsi

Oded's comments

This paper seems to be one of the first that uses the ETH as basis for deriving inapproximability results. This may be a good opportunity to mention a somewhat earlier work of Irit Dinur (ECCC TR16-128), which actually suggests and relies on gap-ETH. Interestingly, in both cases, strong hardness results are derived (regarding problems that seem to have a similar standing within the research community).

Note: In ECCC TR17-063, Benny Applebaum related gap-ETH to ETH (over "smooth instances", which in turn follows from the existence of exponentially-hard one-way functions in NC0).

(Note: I don't recall how it happened that I neglected to comment on the foregoing papers at the time they were posted on ECCC. But this case provides a good demonstration that such neglects do happen, and may not be that rare.)

The original 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^{0.25+\eps})$ 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^{log^{2/3} n}$ (Alon et al., 2011) respectively.

In this work, we show, assuming the exponential time hypothesis (ETH), that there is no polynomial-time algorithm that approximates Densest k-Subgraph to within $n^{1/(loglogn)^c}$ factor of the optimum, where $c>0$ is a universal constant independent of n. In addition, our result has "perfect completeness", meaning that we prove that it is ETH-hard to 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 $n^{-1/(loglogn)^c}$ in polynomial time.

Moreover, if we make a stronger assumption that there is some constant $\eps>0$ such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only $(1-\eps)$-satisfiable (also known as Gap-ETH), then the ratio above can be improved to $n^{f(n)}$ for any function f whose limit is zero as n goes to infinity (i.e. $f=o(1)$).

See ECCC TR16-195.

Back to list of Oded's choices.