Almost Polynomial Hardness of Node-Disjoint Paths in Grids

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

In the classical Node-Disjoint Paths (NDP) problem, we are given an $n$-vertex graph $G=(V,E)$, and a collection $M=\{(s_1,t_1),\dots ,(s_k,t_k)\}$ of pairs of its vertices, called…