论文标题
紧密的条件下限，以在有向图中近似直径
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
论文作者
论文摘要
最基本的图形参数之一是直径，这是任何对顶点之间的最大距离。在强大的指数时间假设（SETH）下，计算具有$ m $边缘的图表的直径需要$ m^{2-o（1）} $时间，这对于非常大的图表可能是刺激性的，因此需要直径的有效近似算法。 有一种民间传说算法，在$ \ tilde {o}（m）$ time中给出了直径为$ 2 $的算法。此外，一系列工作以$ 3/2 $ - APPROXIMATION算法的直径为单位，以加权的有向图，以$ \ tilde {o}（M^{3/2}）$时间运行。已知$ 3/2 $ - Approximation算法在Seth：Roditty和Vassilevska W.下是紧密的Wein和Li的后续工作证明，在塞思（Seth）下，直径为直径的任何$ 5/3-ε$近似算法都需要$ m^{3/2-o（1）} $时间。 然而，民间传说2-抗氧化算法是否很紧，尚不清楚，并且在众多论文中已被明确提出为一个空旷的问题。在这个问题上，Bonnet最近证明，在Seth下，任何$ 7/4-ε$近似都需要$ m^{4/3-o（1）} $，仅适用于定向加权图。 我们通过证明民间传说2-鉴定算法是有条件的最佳选择，从而完全解决了这一问题。在此过程中，我们获得了一系列有条件的下限，并与先前的工作一起提供了一个完整的时间准确性权衡取舍，该折衷与所有已知算法有关有向图的所有已知算法。具体来说，我们证明，在任何$δ> 0 $的情况下，$（\ frac {\ frac {2k-1} {k} - δ）$ - 直径的直径近似算法需要$ M^{\ frac {\ frac {k} {k-1} {k-1} -o（k-1} -o（k-1} -o（1）-o（1）} $ time。
Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with $m$ edges requires $m^{2-o(1)}$ time under the Strong Exponential Time Hypothesis (SETH), which can be prohibitive for very large graphs, so efficient approximation algorithms for Diameter are desired. There is a folklore algorithm that gives a $2$-approximation for Diameter in $\tilde{O}(m)$ time. Additionally, a line of work concludes with a $3/2$-approximation algorithm for Diameter in weighted directed graphs that runs in $\tilde{O}(m^{3/2})$ time. The $3/2$-approximation algorithm is known to be tight under SETH: Roditty and Vassilevska W. proved that under SETH any $3/2-ε$ approximation algorithm for Diameter in undirected unweighted graphs requires $m^{2-o(1)}$ time, and then Backurs, Roditty, Segal, Vassilevska W., and Wein and the follow-up work of Li proved that under SETH any $5/3-ε$ approximation algorithm for Diameter in undirected unweighted graphs requires $m^{3/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 requires $m^{4/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 all known algorithms for directed graphs. Specifically, we prove that under SETH for any $δ>0$, a $(\frac{2k-1}{k}-δ)$-approximation algorithm for Diameter on directed unweighted graphs requires $m^{\frac{k}{k-1}-o(1)}$ time.
