Faster Algorithms for Disjoint Paths in DAGs and Two Disjoint Shortest Paths

Yang Cao, Haoran Qi, Hanzhi Wang

For $k$ vertex-disjoint paths with prescribed endpoints in a directed acyclic graph (DAG), the $O(m{n}^{k-1})$-time pebbling algorithm of Fortune, Hopcroft, and Wyllie [TCS 1980] has…