Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
Settling SETH vs. approximate sparse directed unweighted diameter (up to (NU)NSETH)
复制标题
沉降 SETH 与近似稀疏定向未加权直径（最多 (NU)NSETH）
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Ray Li
中科院分区：
文献类型：
--
作者：
Ray Li
我们证明了几个关于逼近图直径的细粒度复杂性的紧致性结果。首先，我们证明了对于任何ε>；0，在强指数时间假设(SEH)的情况下，即使在未加权的图中，也不存在关于稀疏有向图直径的近线性时间2−ε近似算法。这一结果表明，在Seth下，直径的一个简单的近线性时间2-近似算法是最优的，回答了Rubinstein和Vassilevska-Williams(Sigact‘19)对有向图的调查中的一个问题。在同一次调查中，Rubinstein和Vassilevska-Williams还询问是否有可能证明在O(n1.499)时间内有向图中没有2个直径的−ε近似算法。我们证明，假设一个称为nseth的假设，人们不能使用基于确定性Seth的约简来排除这样的算法的存在。推广这两个结果中的技巧，我们刻画了稀疏有向未加权图直径的2−ε近似算法在O(N1+δ)时间内是否可以通过对每个δ∈(0，1)和基本上每个ε∈(0，1)的确定性的基于SETH的约化来排除。这解决了用于确定性约简的稀疏有向未加权图直径的赛斯硬度，最高可达nseth。我们对基于随机SETH的减少做了同样的描述，假设另一个假设称为NUNSETH。我们证明了无向图的附加硬度和不可约性结果。
We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any ε>0, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time 2−ε-approximation algorithms for the Diameter of a sparse directed graph, even in unweighted graphs. This result shows that a simple near-linear time 2-approximation algorithm for Diameter is optimal under SETH, answering a question from a survey of Rubinstein and Vassilevska-Williams (SIGACT ’19) for the case of directed graphs. In the same survey, Rubinstein and Vassilevska-Williams also asked if it is possible to show that there are no 2−ε approximation algorithms for Diameter in a directed graph in O(n1.499) time. We show that, assuming a hypothesis called NSETH, one cannot use a deterministic SETH-based reduction to rule out the existence of such algorithms. Extending the techniques in these two results, we characterize whether a 2−ε approximation algorithm running in time O(n1+δ) for the Diameter of a sparse directed unweighted graph can be ruled out by a deterministic SETH-based reduction for every δ∈(0,1) and essentially every ε∈(0,1), assuming NSETH. This settles the SETH-hardness of approximating the diameter of sparse directed unweighted graphs for deterministic reductions, up to NSETH. We make the same characterization for randomized SETH-based reductions, assuming another hypothesis called NUNSETH. We prove additional hardness and non-reducibility results for undirected graphs.
登录
查看更多内容
改进工作跨度权衡单一源可达性和近似最短路径
DOI：
10.1145/3350755.3400222
发表时间：
2020
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
有向跳跃集和并行近似最短路径的高效构建
DOI：
10.1145/3357713.3384270
发表时间：
2020
期刊：
ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Cao, Nairen;Fineman, Jeremy T.;Russell, Katina
通讯作者：
Russell, Katina
几乎线性功和平方根深度的并行可达性
DOI：
10.1109/focs.2019.00098
发表时间：
2019
期刊：
Annual Symposium on Foundations of Computer Science (FOCS
影响因子：
--
作者：
Liu, Yang P.;Jambulapati, Arun;Sidford, Aaron
通讯作者：
Sidford, Aaron
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