Almost polynomial hardness of node-disjoint paths in grids

DOI10.1145/3188745.3188772zbMATH Open1427.68021arXiv1711.01980OpenAlexW2963966355MaRDI QIDQ5230375FDOQ5230375

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)

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.

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

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

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)

Cited In (15)

• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Title not available (Why is that?)
• Towards tight(er) bounds for the excluded grid theorem
• A tight lower bound for edge-disjoint paths on planar DAGs
• Title not available (Why is that?)
• An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem
• 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
• Title not available (Why is that?)
• On approximating node-disjoint paths in grids
• Grid recognition: classical and parameterized computational perspectives
• New hardness results for routing on disjoint paths
• New hardness results for routing on disjoint paths

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)