New Hardness Results for Routing on Disjoint Paths

by Julia Chuzhoy, David H.K. Kim and Rachit Nimavat.

Oded's comments

This is a very fancy "iterative" reduction (i.e., fitting the Bravely and Moderately theme). The target instances are two-dimensional grids with holes.

The original abstract

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected n-vertex graph G, and a collection M 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 current negative result is a roughly $\Omega(log^{1/2}n)$-hardness of approximation. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves a $\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 currently known lower bound for both these versions of the problem is APX-hardness.

In this talk we will show that NDP is $2^{\Omega(\log n)}$-hard to approximate, unless all problems in 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. 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.

Back to list of Oded's choices.