Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths

Rajesh Chitnis, Samuel Thomas, Anthony Wirth

Given a graph $G=(V,E)$ and a set $T=\{(s_i,t_i):1\le i\le k\}\subseteq V\times V$ of $k$ pairs, the $k$-vertex-disjoint-paths (resp. $k$-edge-disjoint-paths) problem asks t…