New hardness results for routing on disjoint paths

DOI10.1137/17M1146580MaRDI QIDQ3387753zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, David H. Kim, Rachit Nimavat

Publication date 13 January 2021

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmshardness of approximationdisjoint pathsgraph routing problems

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Abstract: In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $mathcalM=(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 the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(sqrtn)$, while the best current negative result is an $Omega(lo{g}^{1/2-delta}n)$-hardness of approximation for any constant $delta$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $ildeO(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $ildeO(n^{9/19})$. The best currently known lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper we prove that NDP is $2^{Omega(sqrtlogn)}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(logn)}$. Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$, and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related Edge-Disjoint Paths problem, showing the same hardness of approximation ratio even for sub-cubic planar graphs with all sources lying on the boundary of a single face.

Recommendations

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

Cites work

• scientific article; zbMATH DE number 5899246 (Why is no real title available?)
• scientific article; zbMATH DE number 16300 (Why is no real title available?)
• scientific article; zbMATH DE number 1261807 (Why is no real title available?)
• scientific article; zbMATH DE number 910915 (Why is no real title available?)
• A Polylogarithmic Approximation Algorithm for Edge-Disjoint Paths with Congestion 2
• Almost polynomial hardness of node-disjoint paths in grids
• An \(O(\log n)\)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs
• Approximating disjoint-path problems using packing integer programs
• Approximations for the disjoint paths problem in high-diameter planar networks
• Edge Disjoint Paths in Moderately Connected Graphs
• Edge-disjoint paths in planar graphs with constant congestion
• Graph minors. XIII: The disjoint paths problem
• Hardness of the undirected edge-disjoint paths problem
• Improved approximation for node-disjoint paths in planar graphs
• Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
• Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2
• Multicommodity flow, well-linked terminals, and routing problems
• On approximating node-disjoint paths in grids
• On the Complexity of Timetable and Multicommodity Flow Problems
• On the Computational Complexity of Combinatorial Problems
• Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
• Probabilistic checking of proofs
• Proof verification and the hardness of approximation problems
• Randomized rounding: A technique for provably good algorithms and algorithmic proofs
• Routing in undirected graphs with constant congestion

Cited in

(12)

• Logarithmic hardness of the undirected edge-disjoint paths problem
• New results in graph routing
• Approximating maximum integral multiflows on bounded genus graphs
• Search-space reduction via essential vertices
• Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
• New algorithms for maximum disjoint paths based on tree-likeness
• New algorithms for maximum disjoint paths based on tree-likeness
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Almost polynomial hardness of node-disjoint paths in grids
• Almost polynomial hardness of node-disjoint paths in grids
• On approximating node-disjoint paths in grids
• New hardness results for routing on disjoint paths

This page was built for publication: New hardness results for routing on disjoint paths

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