论文标题
多源替换路径问题
Multiple Source Replacement Path Problem
论文作者
论文摘要
图形算法中经典的工作线之一是替代路径问题：给定图形$ g $，$ s $和$ t $，找到从$ s $到$ t $的最短路径，从$ s $到$ t $的最短路径避免了每个边缘$ e $。这些路径在文献中称为替代路径。对于一个未方向且未加权的图（Malik，Mittal和Gupta，《操作研究快报》，1989年）和（Hershberger and Suri，Focs，2001年）设计了一种算法，该算法解决了$ \ tilde O（m+n）$时间的替换路径问题。自然要问我们是否可以推广替换路径问题：{\ em我们可以找到从源$ s $到$ g $中的所有顶点的所有替换路径吗？}这个问题称为单源替换路径问题。 最近（Chechik and Cohen，Soda 2019）设计了一种随机组合算法，该算法在$ \ tilde O中解决了单源替换路径问题（M \ SQRT N \ + N^2）$时间。当有很多消息来源而不是一个问题时，他们的工作没有解决的问题之一。当有$ n $源时，（Bernstein and Karger，STOC 2009）的组合算法可用于在$ \ tilde o（Mn + n^3）$时间中找到所有配对替代路径。但是，没有任何一般$σ$知道的结果。因此，我们研究的问题定义如下：给定一组$σ$来源，我们希望找到从这些来源到$ g $的所有顶点的替换路径。我们为此问题提供了一个随机组合算法，该算法将$ \ tilde o（m \ sqrt {nσ} +\σn^2）$时间。该结果概括了这两个问题已知的结果。我们的算法与众不同，并且可以说要简单（Chechik and Cohen，Soda，2019年）。像他们一样，我们使用布尔矩阵乘法猜想显示了匹配的条件下限。
One of the classical line of work in graph algorithms has been the Replacement Path Problem: given a graph $G$, $s$ and $t$, find shortest paths from $s$ to $t$ avoiding each edge $e$ on the shortest path from $s$ to $t$. These paths are called replacement paths in literature. For an undirected and unweighted graph, (Malik, Mittal, and Gupta, Operation Research Letters, 1989) and (Hershberger and Suri, FOCS 2001) designed an algorithm that solves the replacement path problem in $\tilde O(m+n)$ time. It is natural to ask whether we can generalize the replacement path problem: {\em can we find all replacement paths from a source $s$ to all vertices in $G$?} This problem is called the Single Source Replacement Path Problem. Recently (Chechik and Cohen, SODA 2019) designed a randomized combinatorial algorithm that solves the Single Source Replacement Path Problem in $\tilde O(m\sqrt n\ + n^2)$ time. One of the questions left unanswered by their work is the case when there are many sources, not one. When there are $n$ sources, the combinatorial algorithm of (Bernstein and Karger, STOC 2009) can be used to find all pair replacement path in $\tilde O(mn + n^3)$ time. However, there is no result known for any general $σ$. Thus, the problem we study is defined as follows: given a set of $σ$ sources, we want to find the replacement path from these sources to all vertices in $G$. We give a randomized combinatorial algorithm for this problem that takes $\tilde O(m\sqrt{n σ} +\ σn^2)$ time. This result generalizes both results known for this problem. Our algorithm is much different and arguably simpler than (Chechik and Cohen, SODA 2019). Like them, we show a matching conditional lower bound using the Boolean Matrix Multiplication conjecture.
