论文标题
使用几何镜头找到k最短路径
Using a geometric lens to find k disjoint shortest paths
论文作者
论文摘要
给定一个无方向的$ n $ - vertex图和$ k $终端顶点$（s_1，t_1），\ ldots，（s_k，t_k）$，$ k $ -disjoint最短路径（$ k $ -dsp） - problem询问$ k $ k $ k $ k $ k $ k $ k $ perwisex $ p_1 $ p_1 $ p_i $是最短的$ s_i $ - $ t_i $ - in [k] $ in [k] $的每个$ i \。最近，Lochet [Soda 2021]提供了一种算法，该算法以$ n^{o（k^{5^k}）}} $ time求解$ k $ -dsp，回答了一个20岁的有关$ k $ -dsp的计算复杂性的问题。一方面，我们提出了改进的$ n^{o（k！k）} $ - 基于此问题的新几何视图的时间算法。对于特殊情况，$ k = 2 $在$ m $ - 边缘图上，我们表明可以通过算法的小修改和精制分析将运行时间进一步减少到$ o（nm）$。另一方面，我们证明$ k $ -dsp相对于$ k $是w [1] - 表明多项式运行时间对参数$ k $的依赖性可能是不可避免的。
Given an undirected $n$-vertex graph and $k$ pairs of terminal vertices $(s_1,t_1), \ldots, (s_k,t_k)$, the $k$-Disjoint Shortest Paths ($k$-DSP)-problem asks whether there are $k$ pairwise vertex-disjoint paths $P_1,\ldots, P_k$ such that $P_i$ is a shortest $s_i$-$t_i$-path for each $i \in [k]$. Recently, Lochet [SODA 2021] provided an algorithm that solves $k$-DSP in $n^{O(k^{5^k})}$ time, answering a 20-year old question about the computational complexity of $k$-DSP for constant $k$. On the one hand, we present an improved $n^{O(k!k)}$-time algorithm based on a novel geometric view on this problem. For the special case $k=2$ on $m$-edge graphs, we show that the running time can be further reduced to $O(nm)$ by small modifications of the algorithm and a refined analysis. On the other hand, we show that $k$-DSP is W[1]-hard with respect to $k$, showing that the dependency of the degree of the polynomial running time on the parameter $k$ is presumably unavoidable.
