Improved approximation for node-disjoint paths in planar graphs

DOI10.1145/2897518.2897538MaRDI QIDQ5361861zbMATH OpenOpenAlexFDO

Authors Julia Chuzhoy, David H. Kim, Shi Li

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsnode-disjoint pathsrouting problems

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Programming involving graphs or networks (90C35)

Abstract: We study the classical Node-Disjoint Paths (NDP) problem: given an $n$-vertex graph $G$ and a collection $M=(s_1,t_1),ldots,(s_k,t_k)$ of pairs of vertices of $G$ called demand pairs, find a maximum-cardinality set of node-disjoint paths connecting the demand pairs. NDP is one of the most basic routing problems, that has been studied extensively. Despite this, there are still wide gaps in our understanding of its approximability: the best currently known upper bound of $O(sqrtn)$ on its approximation ratio is achieved via a simple greedy algorithm, while the best current negative result shows that the problem does not have a better than $Omega(lo{g}^{1/2-delta}n)$-approximation for any constant $delta$, under standard complexity assumptions. Even for planar graphs no better approximation algorithms are known, and to the best of our knowledge, the best negative bound is APX-hardness. Perhaps the biggest obstacle to obtaining better approximation algorithms for NDP is that most currently known approximation algorithms for this type of problems rely on the standard multicommodity flow relaxation, whose integrality gap is $Omega(sqrtn)$ for NDP, even in planar graphs. In this paper, we break the barrier of $O(sqrtn)$ on the approximability of the NDP problem in planar graphs and obtain an $ildeO(n^{9/19})$-approximation. We introduce a new linear programming relaxation of the problem, and a number of new techniques, that we hope will be helpful in designing more powerful algorithms for this and related problems.

Recommendations

• scientific article; zbMATH DE number 780786
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Approximations for the disjoint paths problem in high-diameter planar networks
• scientific article; zbMATH DE number 1263178
• On approximating node-disjoint paths in grids
• An improvement of Goldberg, Plotkin and Vaidya's maximal node-disjoint paths algorithm
• On shortest disjoint paths in planar graphs
• On shortest disjoint paths in planar graphs
• A linear-time algorithm for edge-disjoint paths in planar graphs
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs

Cited in

(23)

• Approximations for the disjoint paths problem in high-diameter planar networks
• New algorithms for maximum disjoint paths based on tree-likeness
• A tight lower bound for edge-disjoint paths on planar DAGs
• New hardness results for routing on disjoint paths
• All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs
• Constant congestion routing of symmetric demands in planar directed graphs
• New algorithms for maximum disjoint paths based on tree-likeness
• Improved Approximation Algorithms for Computing k Disjoint Paths Subject to Two Constraints
• New hardness results for routing on disjoint paths
• An Approximation Algorithm for Fully Planar Edge-Disjoint Paths
• Improved approximation for node-disjoint paths in grids with sources on the boundary
• Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
• Shortest k-disjoint paths via determinants
• 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
• Poly-logarithmic approximation for maximum node disjoint paths with constant congestion
• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Kernels for the disjoint paths problem on subclasses of chordal graphs
• Packing cycles in planar and bounded-genus graphs
• An exponential time parameterized algorithm for planar disjoint paths
• Constant approximating disjoint paths on acyclic digraphs is W[1]-hard

This page was built for publication: Improved approximation for node-disjoint paths in planar graphs

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