Theory of Computing
-------------------
Title : Almost Polynomial Hardness of Node-Disjoint Paths in Grids
Authors : Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat
Volume : 17
Number : 6
Pages : 1-57
URL : https://theoryofcomputing.org/articles/v017a006
Abstract
--------
In the classical Node-Disjoint Paths (NDP) problem, we are given an
n-vertex graph G=(V,E), and a collection
M={(s_1,t_1),...,(s_k,t_k)} of pairs of its vertices,
called source-destination, or 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 [Kolliopoulos, Stein, _Math. Progr._2004],
while the best current negative result is a factor
2^{\Omega(\sqrt{\log n})}-hardness of approximation unless
NP\subseteq DTIME(n^{O(\log n)}) [Chuzhoy, Kim, Nimavat, STOC'17],
even if the underlying graph is a _subgraph_ of a grid graph;
unfortunately, this result does not extend to grid graphs. The
approximability of the NDP problem on grid graphs has remained a
tantalizing open question, with the best current upper bound of
\tilde{O}(n^{1/4}), and the best current lower bound of
APX-hardness [Chuzhoy, Kim, APPROX'15] only ruling out a
(1+\delta)-approximation algorithm for some fixed \delta> 0,
assuming that P\neq NP. In this paper we come close to resolving
the approximability of NDP in general, and of NDP in grids in
particular. Our main result is that NDP is
2^{\Omega(\log^{1-\eps}n)-hard to approximate for any constant
\eps, assuming that NP\nsubseteq\DTIME(n^{\poly\log n}), and
that it is n^{\Omega(1/(\log \log n)^2)}-hard to approximate,
assuming that for some constant \delta> 0,
NP \not\subseteq \DTIME(2^{n^{\delta}}).
These results hold even for grid graphs and wall graphs, and extend to
the closely related Edge-Disjoint Paths problem, even in wall 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.