2020/08/19 by Saeed Akhoondian Amiri, Amiri, Saeed Akhoondian, Wargalla, Julian
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2008.08368
openalex publication_date 2020/08/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In the k-Disjoint Shortest Paths problem, a set of terminal pairs of vertices \(si,ti)| 1≤ i≤ k\ is given and we are asked to find paths P1,…,Pk such that each path Pi is a shortest path from si to ti 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) nO(k-c) on DAGs. Using the techniques for DAGs, we show the problem is solvable in time f(k) nO(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)no(k) algorithm for the problem unless ETH fails.