  In the Edge-Disjoint Paths with Congestion problem (EDPwC), we are given an
undirected n-vertex graph G, a collection M={(s_1,t_1),...,(s_k,t_k)} of demand
pairs and an integer c. The goal is to connect the maximum possible number of
the demand pairs by paths, so that the maximum edge congestion - the number of
paths sharing any edge - is bounded by c. When the maximum allowed congestion
is c=1, this is the classical Edge-Disjoint Paths problem (EDP).
  The best current approximation algorithm for EDP achieves an $O(\sqrt
n)$-approximation, by rounding the standard multi-commodity flow relaxation of
the problem. This matches the $\Omega(\sqrt n)$ lower bound on the integrality
gap of this relaxation. We show an $O(poly log k)$-approximation algorithm for
EDPwC with congestion c=2, by rounding the same multi-commodity flow
relaxation. This gives the best possible congestion for a sub-polynomial
approximation of EDPwC via this relaxation. Our results are also close to
optimal in terms of the number of pairs routed, since EDPwC is known to be hard
to approximate to within a factor of $\tilde{\Omega}((\log n)^{1/(c+1)})$ for
any constant congestion c. Prior to our work, the best approximation factor for
EDPwC with congestion 2 was $\tilde O(n^{3/7})$, and the best algorithm
achieving a polylogarithmic approximation required congestion 14.
