## 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.