Tight conditional lower bounds for approximating diameter in directed graphs
Tight conditional lower bounds for approximating diameter in directed graphs
复制标题
有向图中近似直径的严格条件下界
DOI：
10.1145/3406325.3451130
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Wein, Nicole
中科院分区：
文献类型：
--
作者：
Dalirrooyfard, Mina;Wein, Nicole
最基本的图形参数之一是直径，即图形中任意一对顶点之间的最大距离。在强指数时间假设 (SETH) 下，计算带有 medges 的图的直径需要 m2−o(1) 时间，这对于非常大的图来说可能会令人望而却步，因此需要有效的直径近似算法。有一种民间传说算法可以在 Õ(m) 时间内给出直径的 2 近似值（其中 Õ 表示法抑制对数因子）。此外，一系列工作 [SODA’96、STOC’13、SODA’14] 的结论是加权有向图中直径的 3/2 近似算法，运行时间为 Õ(m3/2)。对于有向图，这些是唯一已知的直径近似算法。众所周知，3/2 近似算法在 SETH 下是严格的：Roditty 和 Vassilevska W。[STOC'13] 证明，在 SETH 下，无向无权图中直径的任何 3/2−ε 近似算法需要 m2−o(1) 时间，然后是 Backurs、Roditty、Segal、Vassilevska W. 和Wein [STOC'18] 和 Li 的后续工作证明，在 SETH 下，无向无权图中直径的任何 5/3−ε 近似算法都需要 m3/2−o(1) 时间。然而，民间传说 2 近似算法是否紧是未知的，并且已在许多论文中明确提出为开放问题。针对这个问题，Bonnet 最近证明，在 SETH 下，任何 7/4−ε 近似都需要 m4/3−o(1)，仅适用于有向加权图。我们通过证明民间传说 2 近似算法是条件最优的，彻底解决了有向图的这个问题。在此过程中，我们获得了一系列条件下界，与之前的工作一起，给出了与有向图的三种已知算法紧密结合的完整时间精度权衡。具体来说，我们证明在 SETH 下，对于任何 δ>0，有向无权图上直径的 (2k−1/k−δ) 近似算法需要 mk/k−1−o(1) 时间。
Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices in a graph. Computing the Diameter of a graph withmedges requiresm2−o(1)time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs, so efficientapproximationalgorithms for Diameter are desired.There is a folklore algorithm that gives a 2-approximation for Diameter in Õ(m) time (where Õ notation suppresses logarithmic factors). Additionally, a line of work [SODA’96, STOC’13, SODA’14] concludes with a 3/2-approximation algorithm for Diameter in weighted directed graphs that runs in Õ(m3/2) time. For directed graphs, these are the only known approximation algorithms for Diameter.The 3/2-approximation algorithm is known to be tight under SETH: Roditty and Vassilevska W. [STOC’13] proved that under SETH any 3/2−ε approximation algorithm for Diameter in undirected unweighted graphs requiresm2−o(1)time, and then Backurs, Roditty, Segal, Vassilevska W., and Wein [STOC’18] and the follow-up work of Li proved that under SETH any 5/3−ε approximation algorithm for Diameter in undirected unweighted graphs requiresm3/2−o(1)time.Whether or not the folklore 2-approximation algorithm is tight, however, is unknown, and has been explicitly posed as an open problem in numerous papers. Towards this question, Bonnet recently proved that under SETH, any 7/4−ε approximation requiresm4/3−o(1), only for directed weighted graphs.We completely resolve this question for directed graphs by proving that the folklore 2-approximation algorithm is conditionally optimal. In doing so, we obtain a series of conditional lower bounds that together with prior work, give a complete time-accuracy trade-off that is tight with the three known algorithms for directed graphs. Specifically, we prove that under SETH for any δ>0, a (2k−1/k−δ)-approximation algorithm for Diameter on directed unweighted graphs requiresmk/k−1−o(1)time.
登录
查看更多内容
DOI：
--
发表时间：
2016
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
Massimo Cairo;R. Grossi;Romeo Rizzi
通讯作者：
Romeo Rizzi
DOI：
10.4230/lipics.icalp.2019.46
发表时间：
2019
期刊：
ArXiv
影响因子：
--
作者：
M. Dalirrooyfard;V. V. Williams;Nikhil Vyas;Nicole Wein;Yinzhan Xu;Yuancheng Yu
通讯作者：
Yuancheng Yu
DOI：
--
发表时间：
2015
期刊：
arXiv.org
影响因子：
--
作者：
Amir Abboud;V. V. Williams;Joshua R. Wang
通讯作者：
Joshua R. Wang
计算大型社交网络的直径
DOI：
--
发表时间：
2016
期刊：
International Conference on Supercomputing
影响因子：
--
作者：
Ting;Mei;Wei;B. Wu
通讯作者：
B. Wu
关于计算现实世界有向（加权）图的直径
DOI：
--
发表时间：
2012
期刊：
The Sea
影响因子：
--
作者：
P. Crescenzi;R. Grossi;L. Lanzi;Andrea Marino
通讯作者：
Andrea Marino