Abstract:
We prove a strong inapproximability result for routing on directed graphs with low congestion. Given as input a directed graph on $N$ vertices and a set of source-destination pairs that can be connected via edge-disjoint paths, we prove that it is hard, assuming NP doesn't have $n^{O(\log\log n)}$ time randomized algorithms, to route even a $1/N^{\Omega(1/c(N))}$ fraction of the pairs, even if we are allowed to use each edge on $c(N)$ paths. Here the congestion $c(N)$ can be any function in the range $1 \le c(N) \le \alpha \log N/\log\log N$ for some absolute constant $\alpha > 0$. The hardness result is in the right ballpark since a factor $N^{O(1/c(N))}$ approximation algorithm is known for this problem. An important feature of our result is that it holds with perfect completeness, and shows hardness of low-congestion routing of instances where {\bf all} the input source-destination pairs can be routed on {\em edge-disjoint paths}. Consequently, our result also implies that it is hard to find a routing of all the source-destination pairs that incurs congestion at most $\alpha \log N/\log \log N$, even if there exists an edge-disjoint (i.e., congestion $1$) routing of all the pairs. This shows the optimality, up to constant factors, of the approximation guarantee of the classic Raghavan-Thompson algorithm based on randomized rounding of the fractional multicommodity flow solution.