New Hardness Results for Routing on Disjoint Paths

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected n-vertex graph G, and a collection M=(s1,t1),ldots,(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 Omega(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 tilde O(n1/4)-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is tilde O(n9/19). The best currently known lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper we prove that NDP is 2^Omega(√log n)-hard to approximate, unless all problems in NP have algorithms with running time nO(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 problem, showing the same hardness of approximation ratio even for sub-cubic planar graphs with all sources lying on the boundary of a single face.