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

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 $\{(s_1, t_1), \ldots, (s_k, t_k)\}$ 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 $\Omega(OPT/polylog{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
who gave the first poly-logarithmic approximation
with constant congestion for the Maximum Edge Disjoint Paths
(MEDP) problem.

Joint work with Chandra Chekuri.