Detecting Disjoint Shortest Paths in Linear Time and More

In the k-Disjoint Shortest Paths (k-DSP) problem, we are given a weighted graph G on n nodes and m edges with specified source vertices s₁, , sₖ, and target vertices t₁, , tₖ, and are tasked with determining if G contains vertex-disjoint (sᵢ, tᵢ) -shortest paths. For any constant k, it is known that k-DSP can be solved in polynomial time over undirected graphs and directed acyclic graphs (DAGs). However, the exact time complexity of k-DSP remains mysterious, with large gaps between the fastest known algorithms and best conditional lower bounds. In this paper, we obtain faster algorithms for important cases of k-DSP, and present better conditional lower bounds for k-DSP and its variants. Previous work solved 2-DSP over weighted undirected graphs in O (n⁷) time, and weighted DAGs in O (mn) time. For the main result of this paper, we present linear time algorithms for solving 2-DSP on weighted undirected graphs and DAGs. Our algorithms are algebraic however, and so only solve the detection rather than search version of 2-DSP. For lower bounds, prior work implied that k-Clique can be reduced to 2k-DSP in DAGs and undirected graphs with O ( (kn) ²) nodes. We improve this reduction, by showing how to reduce from k-Clique to k-DSP in DAGs and undirected graphs with O ( (kn) ²) nodes. A variant of k-DSP is the k-Disjoint Paths (k-DP) problem, where the solution paths no longer need to be shortest paths. Previous work reduced from k-Clique to p-DP in DAGs with O (kn) nodes, for p= k + k (k-1) /2. We improve this by showing a reduction from k-Clique to p-DP, for p=k + k²/4. Under the k-Clique Hypothesis from fine-grained complexity, our results establish better conditional lower bounds for k-DSP for all k 4, and better conditional lower bounds for p-DP for all p 4031.