TY - GEN

T1 - Poly-logarithmic approximation for maximum node disjoint paths with constant congestion

AU - Chekuri, Chandra

AU - Ene, Alina

PY - 2013

Y1 - 2013

N2 - 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 polylogarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.

AB - 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 polylogarithmic approximation with constant congestion for the Maximum Edge Disjoint Paths (MEDP) problem.

UR - http://www.scopus.com/inward/record.url?scp=84876018864&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84876018864&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973105.24

DO - 10.1137/1.9781611973105.24

M3 - Conference contribution

AN - SCOPUS:84876018864

SN - 9781611972511

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 326

EP - 341

BT - Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

PB - Association for Computing Machinery

T2 - 24th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013

Y2 - 6 January 2013 through 8 January 2013

ER -