Hardness of Approximate Diameter: Now for Undirected Graphs
Hardness of Approximate Diameter: Now for Undirected Graphs
复制标题
近似直径的硬度：现在适用于无向图
DOI：
10.1109/focs52979.2021.00102
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
V. V. Williams
中科院分区：
文献类型：
--
作者：
M. Dalirrooyfard;Ray Li;V. V. Williams
近似图形直径是一项具有理论和实践意义的基本任务。一个简单的民间传说算法可以通过从任意顶点运行 BFS 来在线性时间内输出直径的 2 近似值。在近线性时间内是否可以有更好的近似值一直是个悬而未决的问题。一系列关于细粒度复杂性的论文导致了有向图中直径的强硬度结果，最终形成了 [Li, STOC'21] 和 [Dalirrooyfard 和 Wein, STOC'21] 最近独立发现的权衡曲线，表明在强指数时间假设 (SETH) 下，对于任何整数 $k\geq 2$ 和 $\delta > 0$， 有向 $m$ 边图中直径的 $2-\frac{1}{k}-\delta$ 近似需要 $mn^{1+1/(k-1)-o(1)}$ 时间。特别是，简单的线性时间 2 近似算法对于有向图来说是最佳的。在本文中，我们证明相同的权衡下界曲线对于无向图也是可能的，扩展了 [Roditty 和 Vassilevska W., STOC'13]、[Li'20] 和 [Bonnet, ICALP'21] 的结果，他们分别证明了曲线的前几种情况，$k=2,3$ 和 4。我们的结果特别表明，简单的线性时间 2 近似算法对于无向图也是最优的。为了获得我们的结果，我们开发了用于细粒度简化的新工具，这些工具可用于证明基于 SETH 的硬度，以解决与距离计算相关的无向图中的其他问题。
Approximating the graph diameter is a basic task of both theoretical and practical interest. A simple folklore algorithm can output a 2-approximation to the diameter in linear time by running BFS from an arbitrary vertex. It has been open whether a better approximation is possible in near-linear time. A series of papers on fine-grained complexity have led to strong hardness results for diameter in directed graphs, culminating in a recent tradeoff curve independently discovered by [Li, STOC'21] and [Dalirrooyfard and Wein, STOC'21], showing that under the Strong Exponential Time Hypothesis (SETH), for any integer $k\geq 2$ and $\delta > 0$, a $2-\frac{1}{k}-\delta$ approximation for diameter in directed $m$-edge graphs requires $mn^{1+1/(k-1)-o(1)}$ time. In particular, the simple linear time 2-approximation algorithm is optimal for directed graphs. In this paper we prove that the same tradeoff lower bound curve is possible for undirected graphs as well, extending results of [Roditty and Vassilevska W., STOC'13], [Li'20] and [Bonnet, ICALP'21] who proved the first few cases of the curve, $k=2,3$ and 4, respectively. Our result shows in particular that the simple linear time 2-approximation algorithm is also optimal for undirected graphs. To obtain our result we develop new tools for fine-grained reductions that could be useful for proving SETH-based hardness for other problems in undirected graphs related to distance computation.
DOI：
10.1145/3406325.3451130
发表时间：
2021
期刊：
STOC 2021: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Dalirrooyfard, Mina;Wein, Nicole
通讯作者：
Wein, Nicole