论文标题
密集的加权挖掘中的近乎最佳的减少SSSP
Near-Optimal Decremental SSSP in Dense Weighted Digraphs
论文作者
论文摘要
在减少单源最短路径问题（SSSP）中，我们得到了一个加权的有向图$ g =（v，e，w）$进行边缘删除和源源顶点$ r \ in V $;令$ n = | v |，m = | e | $和$ w $是图形的长宽比。目标是获得一个数据结构，该数据结构将最短的路径从$ r $到$ v $中的所有顶点，并可以在$ o（1）$ time中回答远程查询，并返回$ o（| p |）$时间的相应路径$ p $。 首先考虑了这个问题和Shiloach [JACM'81]，后者为未加权的无向图提供了总更新时间$ O（MN）$的算法；后来将其扩展到定向加权图[focs'95，stoc'99]。有条件的下限表明$ O（Mn）$实际上是最佳的[ESA'04，focs'14，Stoc'15，Stoc'20]。在突破性的结果中，Forster等人。表明如果允许算法返回$（1+ε）$ - 近似路径，而不是确切的路径[stoc'14，iCalp'15]，则可以实现总更新时间$ Mn^{0.9+O（1）} \ log W $。直到Probst Gutenberg和Wulff-Nilsen [Soda'20]提供了一种新方法，该方法得出了总时间$ \ tilde {o}（\ min {m^{2/3} n^{4/3} n^{4/3} \ log w，（mn）^，（mn）^{7/8} \ log w}）$。 我们的结果基于这种最近的方法，但通过引入更强大的抽象以及不同的核心子例程来克服其局限性。我们的新框架产生了一个减少$（1+ε）$ - 近似SSSP数据结构，总更新时间$ \ tilde {o}（n^2 \ log^4 w）$。因此，对于具有多项式边缘的密集图，我们的算法几乎是最佳的。我们的框架也可以应用于稀疏图，以获取总更新时间$ \ tilde {o}（Mn^{2/3} \ log^3 W）$。 我们的主要技术使我们能够将DAG的SSSP算法转换为通用图的SSSP算法，我们认为这具有影响未来工作的巨大潜力。
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph $G=(V,E,w)$ undergoing edge deletions and a source vertex $r \in V$; let $n = |V|, m = |E|$ and $W$ be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from $r$ to all vertices in $V$ and can answer distance queries in $O(1)$ time, as well as return the corresponding path $P$ in $O(|P|)$ time. This problem was first considered by Even and Shiloach [JACM'81], who provided an algorithm with total update time $O(mn)$ for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS'95, STOC'99]. There are conditional lower bounds showing that $O(mn)$ is in fact near-optimal [ESA'04, FOCS'14, STOC'15, STOC'20]. In a breakthrough result, Forster et al. showed that it is possible to achieve total update time $mn^{0.9+o(1)}\log W$ if the algorithm is allowed to return $(1+ε)$-approximate paths, instead of exact ones [STOC'14, ICALP'15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA'20] provided a new approach for the problem, which yields total time $\tilde{O}(\min{m^{2/3}n^{4/3}\log W, (mn)^{7/8} \log W})$. Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental $(1+ε)$-approximate SSSP data structure with total update time $\tilde{O}(n^2 \log^4 W)$. Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time $\tilde{O}(mn^{2/3} \log^3 W)$. Our main technique allows us to convert SSSP algorithms for DAGs to ones for general graphs, which we believe has significant potential to influence future work.
