论文标题
接近最佳的单个源替换路径问题的最佳算法
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
论文作者
论文摘要
In the Single Source Replacement Paths (SSRP) problem we are given a graph $G = (V, E)$, and a shortest paths tree $\widehat{K}$ rooted at a node $s$, and the goal is to output for every node $t \in V$ and for every edge $e$ in $\widehat{K}$ the length of the shortest path from $s$ to $t$ avoiding $e$. 我们提出了一个$ \ tilde {o}（m \ sqrt {n} + n^2）$ time随机组合算法，用于未加权的有向图。以前，在指示情况下，这种界限才知道固定源和目标节点的替换路径的更容易的问题。 我们针对此问题的新上限与现有的条件组合下限匹配。因此，（假设这些条件下限）我们的结果本质上是最佳的，并且在组合设置中完成了SSRP问题的图片。 我们的算法扩展到小小的理性边缘重量的情况。在这种情况下，我们通过证明任何$ o（Mn^{1/2-ε}）$ time（合并或代数）算法来加强现有的条件下限，对于某些固定的$ε> 0 $，都会为所有对较短的路径（以前仅在此类限制的情况下都知道了一个真正的小路径问题）。
In the Single Source Replacement Paths (SSRP) problem we are given a graph $G = (V, E)$, and a shortest paths tree $\widehat{K}$ rooted at a node $s$, and the goal is to output for every node $t \in V$ and for every edge $e$ in $\widehat{K}$ the length of the shortest path from $s$ to $t$ avoiding $e$. We present an $\tilde{O}(m\sqrt{n} + n^2)$ time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed. Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting. Our algorithm extends to the case of small, rational edge weights. We strengthen the existing conditional lower bounds in this case by showing that any $O(mn^{1/2-ε})$ time (combinatorial or algebraic) algorithm for some fixed $ε>0$ yields a truly subcubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting).
