文章基本信息

标题：Almost Polynomial Hardness of Node-Disjoint Paths in Grids
本地全文：下载
作者：Julia Chuzhoy ; David Hong Kyun Kim ; Rachit Nimavat 等
期刊名称：Theory of Computing
印刷版ISSN：1557-2862
电子版ISSN：1557-2862
出版年度：2021
卷号：17
期号：1
页码：1-57
DOI：10.4086/toc.2021.v017a006
语种：English
出版社：University of Chicago
摘要：In the classical Node-Disjoint Paths (NDP) problem, we are given an n-vertex graph G=(V,E), and a collection M={(s1,t1),…,(sk,tk)} 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(n−−√)-approximation [Kolliopoulos, Stein, Math. Progr. 2004], while the best current negative result is a factor 2Ω(logn√)-hardness of approximation unless NP⊆DTIME(nO(logn)) [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 O~(n1/4), and the best current lower bound of APX-hardness [Chuzhoy, Kim, APPROX'15] only ruling out a (1+δ)-approximation algorithm for some fixed δ>0, assuming that P≠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Ω(log1−ϵn)-hard to approximate for any constant ϵ, assuming that NP⊈DTIME(npolylogn), and that it is nΩ(1/(loglogn)2)-hard to approximate, assuming that for some constant δ>0, NP⊈DTIME(2nδ). 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.
关键词：disjoint paths; graph routing; hardness of approximation