## ETH-hardness of Approximating Densest k-Subgraph

by Pasin Manurangsi

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.