Theory of Computing ------------------- Title : Almost Polynomial Hardness of Node-Disjoint Paths in Grids Authors : Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat Volume : 17 Number : 6 Pages : 1-57 URL : https://theoryofcomputing.org/articles/v017a006 Abstract -------- 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),...,(s_k,t_k)} of pairs of its vertices, called source-destination, or demand pairs. The goal is to route as many of the demand pairs as possible, where to route a pair we need to select a path connecting it, so that all selected paths are disjoint in their vertices. The best current algorithm for NDP achieves an O(\sqrt{n})-approximation [Kolliopoulos, Stein, _Math. Progr._2004], while the best current negative result is a factor 2^{\Omega(\sqrt{\log n})}-hardness of approximation unless NP\subseteq DTIME(n^{O(\log n)}) [Chuzhoy, Kim, Nimavat, STOC'17], even if the underlying graph is a _subgraph_ of a grid graph; unfortunately, this result does not extend to grid graphs. The approximability of the NDP problem on grid graphs has remained a tantalizing open question, with the best current upper bound of \tilde{O}(n^{1/4}), and the best current lower bound of APX-hardness [Chuzhoy, Kim, APPROX'15] only ruling out a (1+\delta)-approximation algorithm for some fixed \delta> 0, assuming that P\neq NP. In this paper we come close to resolving the approximability of NDP in general, and of NDP in grids in particular. Our main result is that NDP is 2^{\Omega(\log^{1-\eps}n)-hard to approximate for any constant \eps, assuming that NP\nsubseteq\DTIME(n^{\poly\log n}), and that it is n^{\Omega(1/(\log \log n)^2)}-hard to approximate, assuming that for some constant \delta> 0, NP \not\subseteq \DTIME(2^{n^{\delta}}). These results hold even for grid graphs and wall graphs, and extend to the closely related Edge-Disjoint Paths problem, even in wall graphs. Our hardness proof performs a reduction from the 3COL(5) problem to NDP, using a new graph partitioning problem as a proxy. Unlike the more standard approach of employing Karp reductions to prove hardness of approximation, our proof is a Cook-type reduction, where, given an input instance of 3COL(5), we produce a large number of instances of NDP, and apply an approximation algorithm for NDP to each of them.