## Almost polynomial hardness of node-disjoint paths in grids

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

#### Oded's comments

Indeed, what has caught my attention is the seemingly essential use
of a Cook-reduction rather than a Karp-reduction.
The reduction solves the input instance by iteratively generating
several reduced instances, when the generation of some of these
instances depends on the solution of prior instances. That is,
the reduction uses the full power of the definition, which allows
not only combining solutions of reduced instances in order to
obtain a solution to the given instance, but rather also for
the generation of additional instances that are all used towards
obtaining such a solution.

#### The original abstract

In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex
graph G, and a collection of pairs of its vertices, called 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(\sqrt{n})$-approximation,
while, until recently, the best negative result was a roughly
$\Omega(\sqrt{\log n})$-hardness of approximation. Recently, an improved
$2^{\Omega(\sqrt{\log n})}$-hardness of approximation for NDP was shown, 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.

The approximability of NDP in grids has remained a tantalizing open question,
with the best upper bound of $\tilde{O}(n^{1/4})$, and the best lower bound
of APX-hardness. In this talk we come close to resolving this question, by
showing an almost polynomial hardness of approximation for NDP in grid
graphs.

Our hardness proof performs a reduction from the 3COL(5) problem to NDP,
using a new graph partitioning problem as a proxy. Unlike the more standard
approach of employing Karp reductions to prove hardness of approximation, our
proof is a Cook-type reduction, where, given an input instance of 3COL(5), we
produce a large number of instances of NDP, and apply an approximation
algorithm for NDP to each of them. The construction of each new instance of
NDP crucially depends on the solutions to the previous instances that were
found by the approximation algorithm.

Back to
list of Oded's choices.