Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion

Chandra Chekuri, Alina Ene

Abstract

We consider the Maximum Node Disjoint Paths (MNDP) problem in undirected graphs. The input consists of an undirected graph G = (V, E) and a collection {(s1, t1), …, (sk, tk)} of k source-sink pairs. The goal is to select a maximum cardinality subset of pairs that can be routed/connected via node-disjoint paths. A relaxed version of MNDP allows up to c paths to use a node, where c is the congestion parameter. We give a polynomial time algorithm that routes Ω(OPT/poly log k) pairs with O(1) congestion, where OPT is the value of an optimum fractional solution to a natural multicommodity flow relaxation. Our result builds on the recent breakthrough of Chuzhoy [17] who gave the first poly-logarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.
BibTeX
@inproceedings{chekuri2013poly,
  author = {Chandra Chekuri and Alina Ene},
  title = {{Poly-logarithmic Approximation for Maximum Node Disjoint Paths with Constant Congestion}},
  booktitle = {SODA},
  year = {2013},
  doi = {10.1137/1.9781611973105.24},
}

Loading related content...

Figure