Almost polynomial hardness of node-disjoint paths in grids

DOI10.1145/3188745.3188772MaRDI QIDQ5230375zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, David H. Kim, Rachit Nimavat

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.01980

zbMATH Keywords

completenessreductionsnetwork design problemscomputation network flowscomputation routing

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Network design and communication in computer systems (68M10)

Abstract: In the classical Node-Disjoint Paths (NDP) problem, we are given an $n$-vertex graph $G=(V,E)$, and a collection $M=(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(sqrtn)$-approximation, while, until recently, the best negative result was a factor $Omega(lo{g}^{1/2-epsilon}n)$-hardness of approximation, for any constant $epsilon$, unless $NPsubseteqZPTIME(n^{polylogn})$. In a recent work, the authors have shown an improved $2^{Omega(sqrtlogn)}$-hardness of approximation for NDP, unless $NPsubseteqDTIME(n^{O(logn)})$, even if the underlying graph is a subgraph of a grid graph, and all source vertices lie on the boundary of the grid. 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 $ildeO(n^{1/4})$, and the best current lower bound of APX-hardness. In this paper we come close to resolving the approximability of NDP in general, and NDP in grids in particular. Our main result is that NDP is $2^{Omega(lo{g}^{1-epsilon}n)}$-hard to approximate for any constant $epsilon$, assuming that $NPotsubseteqRTIME(n^{polylogn})$, and that it is $n^{Omega(1/(loglogn{)}^2)}$-hard to approximate, assuming that for some constant $delta>0$, $NPotsubseteqRTIME(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.

Recommendations

• New hardness results for routing on disjoint paths
• New hardness results for routing on disjoint paths
• On approximating node-disjoint paths in grids
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Improved approximation for node-disjoint paths in planar graphs

Cited in

(15)

• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• scientific article; zbMATH DE number 7561324 (Why is no real title available?)
• Towards tight(er) bounds for the excluded grid theorem
• A tight lower bound for edge-disjoint paths on planar DAGs
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• scientific article; zbMATH DE number 7650316 (Why is no real title available?)
• The hardness of the grid problemGi Under the Routine Resolution Method
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Almost polynomial hardness of node-disjoint paths in grids
• On approximating node-disjoint paths in grids
• New hardness results for routing on disjoint paths
• New hardness results for routing on disjoint paths
• Grid recognition: classical and parameterized computational perspectives

This page was built for publication: Almost polynomial hardness of node-disjoint paths in grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230375)