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( √ 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 log n ). In a recent work, the authors have shown an improved 2 Ω( hardness of approximation for NDP, unless NP ⊆ DTIME(n O (log n) ), even if the underlying graph is a sub-graph 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Õ ( √ log n) -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 Ω(log 1−ϵ n) -hard to approximate for any constant ϵ, assuming that NP RTIME(n poly log n ), and that it is n Ω(1/(log log n) 2 ) -hard to approximate, assuming that for some constant δ > 0, NP RTIME(2 n δ ). These results hold even for grid graphs and * A full version of this paper is available at https://arxiv.org/abs/1711.01980 † Supported in part by NSF grants CCF-1318242 and CCF-1616584. ‡ Supported in part by NSF grants CCF-1318242 and CCF-1616584. § Supported in part by NSF grant CCF-1318242. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. 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. • Theory of computation → Network flows; Routing and network design problems; Problems, reductions and completeness;
When in addition all demand edges have one endpoint at the boundary of the wall, there is an 2 O( √ log n·log log n)approximation REF .
Almost polynomial hardness of node-disjoint paths in grids