Improved Approximation for Node-Disjoint Paths in Grids with Sources on the Boundary.

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^{Omega(sqrt{log n})}$, even if the underlying graph is a sub-graph of a grid, and all source vertices lie on the grid boundary. a follow-up work, the authors further show that NDP-Grid is hard to approximate to within factor $Omega(2^{log^{1-epsilon}n})$ for any constant $epsilon$ under standard complexity assumptions, and to within factor $n^{Omega(1/(loglog 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 loglog 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 $Omega(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.