Almost polynomial hardness of node-disjoint paths in grids

In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G=(V,E), and a collection M={(s₁,t₁),…,(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(√n)-approximation, while, until recently, the best negative result was a factor Ω(log^1/2−єn)-hardness of approximation, for any constant є, unless NP ⊆ ZPTIME(n^{poly logn}). In a recent work, the authors have shown an improved 2^Ω(√logn)-hardness of approximation for NDP, unless NP⊆ DTIME(n^O(logn)), even if the underlying graph is a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. 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 Õ(n^1/4), and the best current lower bound of APX-hardness. In a recent work, the authors showed a 2^Õ(√logn)-approximation algorithm for NDP in grid graphs, if all source vertices lie on the boundary of the grid – a result that can be seen as suggesting that a sub-polynomial approximation may be achievable for NDP in grids. In this paper we show that this is unlikely to be the case, and 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^{Ω(log1−є n)}-hard to approximate for any constant є, assuming that NP⊈RTIME(n^{poly logn}), and that it is n^{Ω (1/(loglogn)2)}-hard to approximate, assuming that for some constant δ>0, NP ⊈RTIME(2^nδ). 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. The construction of each new instance of NDP crucially depends on the solutions to the previous instances that were found by the approximation algorithm.