Given a graph G and a collection of source-sink pairs in G, what is the least integer c such that each source can be connected by a path to its sink, with at most c paths going through an edge? This is known as the congestion minimization problem, and the quantity c is called the congestion. Congestion minimization is one of the most well- tudied NP-hard optimization problems. It is well known that the elegant randomized rounding technique of Raghavan and Thompson can be used to obtain a solution with congestion at most c* + O(log n/log log n) where c* is the optimal congestion. In this paper we show that here exists a \delta > 0 such that no polynomial-time algorithm can guarantee a solution with congestion (c* + \delta log n/log log n) unless NP is contained in ZPTIME(n^{log log n}).
We also study the directed edge-disjoint paths (EDP) problem with congestion. The input to this problem is a graph G and a collection of source-sink pairs in G, along with a congestion parameter c. The goal now is to route as many pairs as possible such that the congestion on each edge is strictly bounded by c. We show that for c ranging from 2 to \Theta(log n/log log n), directed EDP with congestion is n^{\Omega(1/c)}-hard to approximate, even if the algorithm performance is compared to the optimal EDP solution with no congestion. We also give a very simple integrality gap construction that shows that the multicommodity-flow relaxation for directed EDP with congestion c has an integrality gap of n^{\Omega(1/c)} for c ranging from 2 to \Theta (log n/log log n). We note that it is known that this problem can be approximated to within n^{O(1/c)} using the multicommodity-flow relaxation.
A surprising aspect of our hardness and integrality gap results for directed EDP with congestion is that the instances created have a unique paths property, namely, for each source-sink pair, there is a unique path connecting it in the instance. An immediate consequence of this property is that our hardness results also hold for the All-or-Nothing Flow problem where the requirement that each pair be routed along a single path is relaxed to sending a unit of flow between each pair. This is in a sharp contrast to the undirected setting where the All-or-Nothing flow problem is known to be approximable to within a poly-logarithmic factor. We note that our hardness results can be extended to the vertex versions of the respective problems, where congestion is measured on vertices and not edges of the input graphs. All our results hold on directed acyclic graphs.
