BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Almost Polynomial Hardness of Node-Disjoint Paths in Grids Nimavat, Rachit


We study the hardness of the Node-Disjoint Paths (NDP) problem. In this problem, we are given a graph and a collection of source-sink pairs of vertices, called demand pairs. The goal is to route as many of the demand pairs as possible, along paths which are disjoint in their vertices. The best current algorithm for NDP achieves a factor O(\sqrt{n})-approximation. In a recent work, we showed a 2^{\Omega(\sqrt{log n})}-hardness of approximation for NDP, improving the best previous hardness bound of roughly \Omega(\sqrt{\log n}) by Andrews et al. This new hardness result holds even for subgraphs of grid graphs, but unfortunately it does not extend to grids themselves. The question of approximability of NDP on grid graphs has remained widely open, with the best current upper bound of O(n^{1/4}), and the best current lower bound of APX-hardness. In this talk I will present a new result that comes close to resolving the approximability of NDP in general, and of NDP grids in particular. We show that NDP is hard to approximate to within near-polynomial factors, even in grid graphs. We also obtain similar hardness of approximation results for the closely related Edge-Disjoint Paths (EDP) problem, even in wall graphs. Joint work with Julia Chuzhoy and David H. K. Kim.

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International