New hardness results for routing on disjoint paths

DOI10.1137/17M1146580zbMATH Open1497.68221arXiv1611.05429OpenAlexW3113475418MaRDI QIDQ3387753FDOQ3387753

Authors: Julia Chuzhoy, David H. Kim, Rachit Nimavat 

Publication date: 13 January 2021

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

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.

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

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

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)

Cites Work

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

Cited In (11)

• 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
• 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)