Revised: April 9, 2020

Published: September 22, 2021

**Keywords:**disjoint paths, graph routing, hardness of approximation

**ACM Classification:**F.2.2, G.2.2, G.1.6, F.1.3

**AMS Classification:**68Q17, 68Q25, 68W25

**Abstract:**
[Plain Text Version]

In the classical Node-Disjoint Paths (NDP) problem, we are given
an $n$-vertex graph $G=(V,E)$, and a collection
$\mset=\set{(s_1,t_1),\ldots,(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^{\polylog 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.