Open Collections

Almost Polynomial Hardness of Node-Disjoint Paths in Grids

Banff International Research Station for Mathematical Innovation and Discovery

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.

Mathematics; Computer science; Operations research, mathematical programming; Theoretical computer science

video/mp4

Author affiliation: Toyota Technological Institute at Chicago

2018-05-16

Attribution-NonCommercial-NoDerivatives 4.0 International

http://hdl.handle.net/2429/65916

Unreviewed

http://creativecommons.org/licenses/by-nc-nd/4.0/