Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
Deterministic Partially Dynamic Single Source Shortest Paths in Weighted Graphs
复制标题
加权图中的确定性部分动态单源最短路径
DOI：
10.4230/lipics.icalp.2017.44
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
A. Bernstein
中科院分区：
文献类型：
--
作者：
A. Bernstein
在本文中，我们考虑递减的单源最短路径（SSSP）问题，其中给定一个图$G$和一个源节点$s$的目标是保持最短的距离$s$和所有其他节点在$G$下的一系列在线对抗边删除。在他们的开创性的工作中，Even和Shiloach [JACM 1981]提出了一个精确的解决方案，解决了未加权图中所有边删除的总更新时间只有O（mn）$的问题。他们的经典算法是递减SSSP问题三十年来的最新技术，即使在允许近似最短路径的情况下。
一系列的结果表明，如果允许近似，如何改进$O（mn）$，最终在Henzinger，Krinninger和Nanongkai [FOCS 14]最近的突破中达到高潮，他们提出了一个$总更新时间接近线性的无向赋权图的（1+\n）$-近似算法：$O（m^{1+o（1）}\log（W））$，其中$W$是图中最重边与最轻边的权重之比。在本文中，他们提出了一个主要的开放问题的问题去随机化他们的结果。
直到最近，所有已知的Even-Shiloach算法的改进都是随机的，并且需要假设非自适应对手。在STOC 2016中，伯恩斯坦和Zohik展示了第一个超过$O（mn）$总更新时间的确定性算法：该算法也是$（1+\n）$-近似的，总更新时间为$\tilde{O}（n^2）$。在SODA 2017中，同一作者提出了一个总更新时间为$\tilde{O}（mn^{3/4}）$的算法。然而，这两种算法都局限于无向，无权图。我们提出的\n {第一}确定性算法的\n {加权}无向图超越$O（mn）$界。总更新时间为$\tilde{O}（n^2 \log（W））$。
In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph $G$ and a source node $s$ the goal is to maintain shortest distances between $s$ and all other nodes in $G$ under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem in unweighted graphs with only $O(mn)$ total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed.
A series of results showed how to improve upon $O(mn)$ if approximation is allowed, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a $(1+\epsilon)$-approximate algorithm for undirected weighted graphs whose total update time is near linear: $O(m^{1+o(1)}\log(W))$, where $W$ is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result.
Until very recently, all known improvements over the Even-Shiloach algorithm were randomized and required the assumption of a non-adaptive adversary. In STOC 2016, Bernstein and Chechik showed the first \emph{deterministic} algorithm to go beyond $O(mn)$ total update time: the algorithm is also $(1+\epsilon)$-approximate, and has total update time $\tilde{O}(n^2)$. In SODA 2017, the same authors presented an algorithm with total update time $\tilde{O}(mn^{3/4})$. However, both algorithms are restricted to undirected, unweighted graphs. We present the \emph{first} deterministic algorithm for \emph{weighted} undirected graphs to go beyond the $O(mn)$ bound. The total update time is $\tilde{O}(n^2 \log(W))$.