Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
Almost-polynomial ratio ETH-hardness of approximating densest k-subgraph
复制标题
DOI：
10.1145/3055399.3055412
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
Pasin Manurangsi
中科院分区：
文献类型：
--
作者：
Pasin Manurangsi
在Denk-Subgraph（DkS）问题中，给定一个无向图G和一个整数k，目标是找到G在k个顶点上的一个子图，该子图包含最多条边。尽管Bhaskara et al.的国家的最先进的算法的问题，实现了只有O（n1/4 + n2）的近似比，以前的尝试证明的硬度的近似，包括那些在平均情况下的假设，未能实现一个多项式的比例;排除在任何最坏情况下的假设和任何平均情况下的假设下的最佳比例只是任何常数（Raghavendra和Steurer）和2 O（log 2/3 n）（Alon等人）。分别在这项工作中，我们表明，假设指数时间假设（ETH），有没有多项式时间算法，近似Denk-Subgraph的最佳n1/（loglogn）c因子内，其中c > 0是一个独立于n的普适常数。此外，我们的结果具有完美的完整性，这意味着我们证明了它是ETH-困难的，甚至区分的情况下，其中G包含一个k-团和的情况下，其中每个诱导的k-子图G的密度最多为1/n-1/（loglogn）c在多项式时间。此外，如果我们做一个更强的假设，即存在某个常数µ > 0，使得没有次指数时间算法可以区分可满足的3SAT公式和仅（1 - ε）-可满足的3SAT公式（也称为Gap-ETH），那么上述比率可以改进为nf（n），对于任何函数f，当n趋于无穷大时，其极限为零（即f o（1））。
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. 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 n1/(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 1/n-1/(loglogn)c in polynomial time. Moreover, if we make a stronger assumption that there is some constant ε > 0 such that no subexponential-time algorithm can distinguish between a satisfiable 3SAT formula and one which is only (1 - ε)-satisfiable (also known as Gap-ETH), then the ratio above can be improved to nf(n) for any function f whose limit is zero as n goes to infinity (i.e. f ϵ o(1)).