Volume 17 (2021) Article 6 pp. 1-57

Almost Polynomial Hardness of Node-Disjoint Paths in Grids

by Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat

Received: August 2, 2018
Revised: April 9, 2020
Published: September 22, 2021

$\newcommand{\P}{\mathsf P} \newcommand{\NP}{\mathsf{NP}} \newcommand{\APX}{\mathsf{APX}} \newcommand{\DTIME}{\mathsf{DTIME}} \newcommand{\set}[1]{\left\{ #1 \right\}} \newcommand{\mset}{{\mathcal M}} \newcommand{\eps}{\epsilon} \newcommand{\polylog}{\operatorname{polylog}}$

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.

DOI: 10.4086/toc.2021.v017a006

© 2021 Julia Chuzhoy, David Hong Kyun Kim, and Rachit Nimavat
Licensed under a Creative Commons Attribution License (CC-BY)