Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
Pasin Manurangsi · 2017
In the Densest k-Subgraph (DkS) 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 Bhaskara et al.'s state-of-the-art algorithm for the problem achieves only O(n1/4 + ϵ) approximation ratio, 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) and 2O(log2/3 n) (Alon et al.) respectively.