In the classical node-disjoint paths (\sf NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection ${\mathcal M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(\sqrt n)$, while the best previous negative result is an $\Omega(\log^{1/2-\delta}n)$-hardness of approximation for any constant $\delta$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $\tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $\tilde O(n^{9/19})$. The best previous lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper, we prove that \sf NDP is $2^{\Omega(\sqrt{\log n})}$-hard to approximate, unless all problems in \sf NP have algorithms with running time $n^{O(\log n)}$. Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$, and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related edge-disjoint paths (\sf EDP) problem, showing the same hardness of approximation ratio even for subcubic planar graphs with all sources lying on the boundary of a single face.

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 source-destination, or demand pairs, find a maximum-cardinality set of mutually node-disjoint paths that connect the demand pairs. The best current approximation for the problem is achieved by a simple greedy $O(\sqrt{n})$-approximation algorithm. A special case of the problem called NDP-Grid, where the underlying graph is a grid, has been studied extensively. The best current approximation algorithm for NDP-Grid achieves an $\tilde{O}(n^{1/4})$-approximation factor. On the negative side, a recent result by the authors shows that NDP is hard to approximate to within factor $2^{Ω(\sqrt{\log n})}$, even if the underlying graph is a sub-graph of a grid, and all source vertices lie on the grid boundary. In a follow-up work, the authors further show that NDP-Grid is hard to approximate to within factor $Ω(2^{\log^{1-ε}n})$ for any constant $ε$ under standard complexity assumptions, and to within factor $n^{Ω(1/(\log\log n)^2)}$ under randomized ETH. In this paper we study NDP-Grid, where all source vertices {s_1,...,s_k} appear on the grid boundary. Our main result is an efficient randomized $2^{O(\sqrt{\log n} \cdot \log\log n)}$-approximation algorithm for this problem. We generalize this result to instances where the source vertices lie within a prescribed distance from the grid boundary. Much of the work on approximation algorithms for NDP relies on the multicommodity flow relaxation of the problem, which is known to have an $Ω(\sqrt n)$ integrality gap, even in grid graphs. Our work departs from this paradigm, and uses a (completely different) linear program only to select the pairs to be routed, while the routing itself is computed by other methods.

In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G=(V,E), and a collection M={(s1,t1),…,(sk,tk)} 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 Ω(log1/2−єn)-hardness of approximation, for any constant є, unless NP ⊆ ZPTIME(npoly logn). In a recent work, the authors have shown an improved 2Ω(√logn)-hardness of approximation for NDP, unless NP⊆ DTIME(nO(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.

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected n-vertex graph G, and a collection M={(s1,t1),…,(sk,tk)} of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is O(√n), while the best current negative result is an Ω(log1/2-δn)-hardness of approximation for any constant δ, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an Õ(n1/4)-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is Õ(n9/19). The best currently known lower bound for both these versions of the problem is APX-hardness.