Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary

Julia Chuzhoy, David H. K. Kim, Rachit Nimavat

We study the classical Node-Disjoint Paths (NDP) problem: given an undirected $n$-vertex graph G, together with a set {(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices, called sou…