论文标题
定居塞思（Seth vs.
Settling SETH vs. Approximate Sparse Directed Unweighted Diameter (up to (NU)NSETH)
论文作者
论文摘要
我们证明了近似图直径的细粒复杂性的几个紧张结果。首先，我们证明，对于任何$ \ varepsilon> 0 $，假设有强大的指数时间假设（SETH），即使在未摩托图中，也没有近2- \ varepsilon $ - varepsilon $ -Approximatimatimatimation $ -2- \ varepsilon $ -approximation算法。该结果表明，在塞思（Seth）下，直径的简单近线性时间2-抗直径算法是最佳的，这回答了鲁布林斯坦和瓦西莱夫斯卡·威廉姆斯（Vassilevska-Williams）的调查中的一个问题（Sigact '19）。 在同一项调查中，鲁宾斯坦和瓦西尔维斯卡 - 威廉姆斯还询问是否有可能表明在$ O（n^{1.499}）中的有向图中的直径没有$ 2- \ varepsilon $近似算法。我们表明，假设一个称为NSETH的假设，不能使用确定性的基于Seth的还原来排除这种算法的存在。 扩展这两个结果中的技术，我们表征了$ 2- \ varepsilon $近似算法在时间$ o（n^{1+δ}）$中运行的稀疏指导图直径是否可以通过确定性的SETH的基于确定性的SETH减少（0.0,0,1）$来排除假设Nseth $ \ varepsilon \ in（0,1）$。这解决了近似稀疏的定向未加权图直径以确定性减少的直径的塞思·hard，最多NSETH。假设另一个称为Nunseth的假设，我们对基于SETH的随机减少进行了相同的特征。 我们证明了无向图的额外硬度和不可还原性结果。
We prove several tight results on the fine-grained complexity of approximating the diameter of a graph. First, we prove that, for any $\varepsilon>0$, assuming the Strong Exponential Time Hypothesis (SETH), there are no near-linear time $2-\varepsilon$-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-\varepsilon$ approximation algorithms for Diameter in a directed graph in $O(n^{1.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-\varepsilon$ approximation algorithm running in time $O(n^{1+δ})$ for the Diameter of a sparse directed unweighted graph can be ruled out by a deterministic SETH-based reduction for every $δ\in(0,1)$ and essentially every $\varepsilon\in(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.
