论文标题
新算法和硬度，用于导向图中的增量单源最短路径
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
论文作者
论文摘要
在动态的单源最短路径（SSSP）问题中，我们获得了一个图形$ g =（v，e）$，约束v $中的边缘插入和删除以及源顶点$ s \ s source dertex $ s \，目标是维持所有$ t \ in V $中的$ d $ d（s，t）$。 细粒度的复杂性为完全动态的SSSP提供了强大的下限，并近似完全动态的SSSP [ESA'04，focs'14，STOC'15]。因此，非常重点是寻找有效的部分动态$（1+ε）$ - 近似SSSP算法[STOC'14，ICALP'15，SODA'14，FOCS'14，Stoc'16，STOC'16，Soda'17，Soda'17，Icalp'17，Icalp'17，Icalp'19，ICALP'19，ICTORP'19，ICTOC'19，Stoc'19，Stoc'19，Stoc'19，Soda'20，Soda'20，Soda'20，Soda'20，Soda'20]。尽管有丰富的文献，但对于定向图，对于$（1+ε）$ - 近似动态SSSP的确定性算法尚无确定性算法，该算法比经典的ES-Tree（JACM'81]表现更好。我们提出第一种这样的算法。 我们提供了加权挖掘中的增量SSSP的数据结构，其中总更新时间$ \ tilde {o}（n^2 \ log w）$，对于非常密集的图形而言是近距离的；在这里，$ W $是图表中最大的重量与最小的比例。我们的算法还改进了Henzinger等人的定向SSSP的最著名的部分动态\ emph {随机}算法。 [stoc'14，ialp'15]如果$ m =ω（n^{1.1}）$。 我们还提供了有条件的下限。 Henzinger等。 [stoc'15]表明，在OMV假设下，在非方向图中，部分动态的$ s $ - $ t $最短路径问题需要摊销的更新或查询时间$ m^{1/2-o（1）} $，给定多项式预处理时间。在有关查找集团的假设下，我们将多项式预处理时间的算法提高了更新和查询下限，以$ m^{0.626-o（1）} $。此外，在$ k $循环假设下，我们表明任何具有$ o（m^{2-ε}）$预处理时间的任何部分动态SSSP算法都需要摊销更新或查询时间$ m^{1-o（1-o（1）} $。
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph $G=(V,E)$ subject to edge insertions and deletions and a source vertex $s\in V$, and the goal is to maintain the distance $d(s,t)$ for all $t\in V$. Fine-grained complexity has provided strong lower bounds for exact partially dynamic SSSP and approximate fully dynamic SSSP [ESA'04, FOCS'14, STOC'15]. Thus much focus has been directed towards finding efficient partially dynamic $(1+ε)$-approximate SSSP algorithms [STOC'14, ICALP'15, SODA'14, FOCS'14, STOC'16, SODA'17, ICALP'17, ICALP'19, STOC'19, SODA'20, SODA'20]. Despite this rich literature, for directed graphs there are no known deterministic algorithms for $(1+ε)$-approximate dynamic SSSP that perform better than the classic ES-tree [JACM'81]. We present the first such algorithm. We present a \emph{deterministic} data structure for incremental SSSP in weighted digraphs with total update time $\tilde{O}(n^2 \log W)$ which is near-optimal for very dense graphs; here $W$ is the ratio of the largest weight in the graph to the smallest. Our algorithm also improves over the best known partially dynamic \emph{randomized} algorithm for directed SSSP by Henzinger et al. [STOC'14, ICALP'15] if $m=ω(n^{1.1})$. We also provide improved conditional lower bounds. Henzinger et al. [STOC'15] showed that under the OMv Hypothesis, the partially dynamic exact $s$-$t$ Shortest Path problem in undirected graphs requires amortized update or query time $m^{1/2-o(1)}$, given polynomial preprocessing time. Under a hypothesis about finding Cliques, we improve the update and query lower bound for algorithms with polynomial preprocessing time to $m^{0.626-o(1)}$. Further, under the $k$-Cycle hypothesis, we show that any partially dynamic SSSP algorithm with $O(m^{2-ε})$ preprocessing time requires amortized update or query time $m^{1-o(1)}$.
