Abstract

Given as input a directed graph on N vertices and a set of source-destination pairs, we study the problem of routing the maximum possible number of source-destination pairs on paths, such that at most c(N) paths go through any edge. We show that the problem is hard to approximate within an NΩ(1/c(N)) factor even when we compare to the optimal solution that routes pairs on edge-disjoint paths, assuming NP doesn’t have NO(log log N)-time randomized algorithms. Here the congestion c(N) can be any function in the range 1 6 c(N) 6 αlogN/loglogN for some absolute constant α>0. The hardness result is in the right ballpark since a factor NO(1/c(N)) approximation algorithm is known for this problem, via rounding a natural multicommodity-flow relaxation. We also give a simple integrality gap construction that shows that the multicommodity-flow relaxation has an integrality gap of NΩ(1/c) for c ranging from 1 to Θ( log n log log n).