## 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.