Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
type: Item
instance of: scholarly article
title: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs
zbMATH Open document ID: 1240.68113
author: Julia Chuzhoy
author: Venkatesan Guruswami
author: Sanjeev Khanna
author: Kunal Talwar
author: Lisa Zhang
author: Matthew Andrews
published in: Combinatorica
publication date: 2011-12-19T00:00:00Z
review text: In the edge-disjoint paths (EDPs) problem, a graph \(G\) and a set of pairs of vertices, called terminals, are given. The objective is to connect as many pairs as possible via edge-disjoint paths. Even highly restricted cases of EDPs correspond to well-studied important optimization problems. In this paper, undirected EDPs are studied, together with a natural generalization known as edge-disjoint paths with congestion (EDPwC), in which the goal is to route as many terminal pairs as possible subject to the constraint that at most \(c\) paths are routed through any edge. For \(c = 1\), the problem is simply the EDPs problem. In this paper, the hardness of EDPwC in undirected graphs is studied. The main result is that, for every \(\epsilon > 0\), there exists an \(\alpha > 0\) such that, for \(1\leq c \leq \alpha \log \log V/\log \log \log V\), it is hard to distinguish between instances where we can route all terminal pairs on edge-disjoint paths, and instances where we can route at most a fraction \(1/(\log V )^{(1-\varepsilon)/(c+2)}\) of the terminal pairs, even if we allow for a congestion \(c\). This implies a hardness of approximation of \( (\log V )^{(1-\varepsilon)/(c+2)}\) for EDPwC and a hardness of approximation of \(\Omega (\log \log V/\log \log \log V )\) for the undirected congestion minimization problem. Another related problem is the all-or-nothing (ANF) flow problem where each routed demand is allowed to be routed on fractional paths. ANF is a relaxation of EDPs. The last problem discussed in this paper is the congestion minimization problem in which the goal is to find the minimum value of the congestion \(c\) such that all terminal pairs can be routed. An \(\Omega ((\log V)^{1/2-\varepsilon} )\) inapproximability result for EDPs, ANF, and node-disjoint paths on undirected graphs is shown for any constant \(\varepsilon>0\). If a congestion \(c\), \(1\leq c \leq O( \log \log V/\log \log \log V)\), is allowed in the routing, a hardness factor of \( (\l…
reviewed by: Ioan Tomescu
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C21
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 5990603
zbMATH Keywords: disjoint paths problem with congestion
zbMATH Keywords: routing
zbMATH Keywords: approximability ratio
zbMATH Keywords: approximation algorithm
zbMATH Keywords: randomized rounding
zbMATH Keywords: all-or-nothing flow problem
zbMATH Keywords: congestion minimization problem
zbMATH Keywords: constraint satisfaction problem
zbMATH Keywords: multicommodity flow relaxation
zbMATH Keywords: random hypergraph
MaRDI profile type: Publication
full work available at URL: s00493-010-2455-9
OpenAlex ID: W2122997342
cites work: Hardness of the undirected edge-disjoint paths problem
cites work: Hardness of the undirected congestion minimization problem
cites work: Logarithmic hardness of the directed congestion minimization problem
cites work: An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
cites work: Q4537731
cites work: Approximation algorithms for disjoint paths and related routing and packing problems
cites work: The all-or-nothing multicommodity flow problem
cites work: Edge-disjoint paths in Planar graphs with constant congestion
cites work: Multicommodity flow, well-linked terminals, and routing problems
cites work: Q3002769
cites work: Q4471352
cites work: Multicommodity demand flow in a tree and packing integer programs
cites work: Q3549611
cites work: The Nonapproximability of Non-Boolean Predicates
cites work: Q5725269
cites work: Edge-disjoint paths in planar graphs
cites work: The directed subgraph homeomorphism problem
cites work: Approximability of Packing Disjoint Cycles
cites work: Q4198056
cites work: Primal-dual approximation algorithms for integral flow and multicut in trees
cites work: Near-optimal hardness results and approximation algorithms for edge-disjoint paths and related problems
cites work: Q3002760
cites work: Simple analysis of graph tests for linearity and PCP
cites work: Approximations for the disjoint paths problem in high-diameter planar networks
cites work: Q4231910
cites work: An overtraining-resistant stochastic modeling method for pattern recognition
cites work: Q3840354
cites work: Approximation algorithms for cycle packing problems
cites work: Randomized rounding: A technique for provably good algorithms and algorithmic proofs
cites work: A Parallel Repetition Theorem
cites work: Q3972953
cites work: A PCP characterization of NP with optimal amortized query complexity
cites work: Q5501283
DOI: 10.1007/S00493-010-2455-9
description: scientific article; zbMATH DE number 5990603