Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest PathsResearch Paper
In the k vertex-disjoint paths problem (k-DP) the input is a directed graph with vertices, edges and terminal pairs , and the task is to connect every pair by a path so that the paths are pairwise vertex-disjoint. In the k disjoint shortest paths problem (k-DSP) every path must in addition be a shortest path between its terminals. Already for…