TR06-141 Authors: Venkatesan Guruswami, Kunal Talwar

Publication: 23rd November 2006 04:04

Downloads: 2923

Keywords:

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.