论文标题
脱节最短的路径与dag的交通拥堵
Disjoint Shortest Paths with Congestion on DAGs
论文作者
论文摘要
在k-diseeent最短路径问题中，给出了一组终端对顶点$ \ {（s_i，t_i）\ mid 1 \ le i i \ le i \ le K \} $其中之一。我们介绍了问题的概括，即，$ k $ - disexhint最短的路径与拥堵-c $，其中每个顶点都可以路由$ c $路径。 我们提供了一种简单的算法来解决时间$ f（k）n^{o（k-c）} $的问题。使用DAGS的技术，我们表明在一般无向图上的时间$ f（k）n^{o（k）} $可以解决问题。我们的DAGS算法基于$ k $ -dischoint的算法，带有拥堵 - $ C $ [IPL2019]，但我们大大简化了他们的论点。 然后，我们证明无法通过证明每个常数$ c $的问题是W [1] -Hard W.R.T. \参数$ K-C $来显着改善算法。我们还考虑了无环平面图上的问题，但是这次我们将自己限制在边缘最短路径问题上。我们表明，即使在无环平面图上，除非ETH失败，否则没有$ f（k）n^{o（k）} $算法。
In the k-Disjoint Shortest Paths problem, a set of terminal pairs of vertices $\{(s_i,t_i)\mid 1\le i\le k\}$ is given and we are asked to find paths $P_1,\ldots,P_k$ such that each path $P_i$ is a shortest path from $s_i$ to $t_i$ and every vertex of the graph routes at most one of them. We introduce a generalization of the problem, namely, $k$-Disjoint Shortest Paths with Congestion-$c$ where every vertex is allowed to route up to $c$ paths. We provide a simple algorithm to solve the problem in time $f(k) n^{O(k-c)}$ on DAGs. Using the techniques for DAGs, we show the problem is solvable in time $f(k) n^{O(k)}$ on general undirected graphs. Our algorithm for DAGs is based on the earlier algorithm for $k$-Disjoint Paths with Congestion-$c$[IPL2019], but we significantly simplify their argument. Then we prove that it is not possible to improve the algorithm significantly by showing that for every constant $c$ the problem is W[1]-hard w.r.t.\ parameter $k-c$. We also consider the problem on acyclic planar graphs, but this time we restrict ourselves to the edge-disjoint shortest paths problem. We show that even on acyclic planar graphs there is no $f(k)n^{o(k)}$ algorithm for the problem unless ETH fails.
