论文标题
减少近似路径的确定性算法：更快，更简单
Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
论文作者
论文摘要
In the decremental $(1+ε)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s \in V$, and we are asked to process edge deletions efficiently and answer queries for distance estimates $ \ widetilde {\ MathBf {dist}} _ g（s，v）$在v $中的每个阶段，在任何阶段，因此，$ \ mathbf {dist} _g（s，s，v） ε）\ Mathbf {dist} _g（s，v）$。在减少$（1+ε）$ - 近似全对最短路径（APSP）问题中，我们被要求回答距离估计值$ \ widetilde {\ mathbf {dist}} _ g（u，v）$ in v $中的每个$ u，v \ in v $。在本文中，我们考虑了未指向，未加权图的问题。 我们提供了一个新的\ emph {确定性}算法，用于减少$（1 +ε）$ - 近似SSSP问题，该问题需要总更新时间$ o（mn^{0.5 + o（1）}）$。我们的算法在Chechik和Bernstein [STOC 2016]的当前最佳算法上有改进的算法，并具有总更新时间$ \ tilde {o}（n^2）$，以及使用运行时间$ \ tilde $ \ tilde {o}（n^o}（n^o}（n^n^1.25} $}的稀疏图的最佳现有算法$ m = o（n^{1.5 -o（1）}）$。 为了获得这种新算法，我们开发了几种新技术，包括改进的图形的减少覆盖数据结构，对Chechik和Bernstein引入的重/光分解框架的更有效概念以及伯恩斯坦引入的重量/光线分解框架以及在确定性设置中保持动态\ emph {Sparse}模拟器的首个聚类技术。 作为一种副产品，我们还获得了一种新的简单确定性算法，用于减少$（1+ε）$ - 近似apsp问题，近乎最佳的总运行时间$ \ tilde {o}（Mn /ε）$与Henzinger，Forster和Nananongkai的复杂性相匹配，却涉及复杂的时间复杂性，但
In the decremental $(1+ε)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s \in V$, and we are asked to process edge deletions efficiently and answer queries for distance estimates $\widetilde{\mathbf{dist}}_G(s,v)$ for each $v \in V$, at any stage, such that $\mathbf{dist}_G(s,v) \leq \widetilde{\mathbf{dist}}_G(s,v) \leq (1+ ε)\mathbf{dist}_G(s,v)$. In the decremental $(1+ε)$-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates $\widetilde{\mathbf{dist}}_G(u,v)$ for every $u,v \in V$. In this article, we consider the problems for undirected, unweighted graphs. We present a new \emph{deterministic} algorithm for the decremental $(1+ε)$-approximate SSSP problem that takes total update time $O(mn^{0.5 + o(1)})$. Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time $\tilde{O}(n^2)$ and the best existing algorithm for sparse graphs with running time $\tilde{O}(n^{1.25}\sqrt{m})$ [SODA 2017] whenever $m = O(n^{1.5 - o(1)})$. In order to obtain this new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic \emph{sparse} emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental $(1+ε)$-approximate APSP problem with near-optimal total running time $\tilde{O}(mn /ε)$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].
