Hardness of the Edge-Disjoint Paths Problem with Congestion
01 January 2005
In the Edge-Disjoint Paths problem with Congestion (EDPwC), we are given a graph with $M$ edges and a set of terminal pairs. The objective is to route as many terminal pairs as possible subject to the constraint that at most $w$ demands can be routed through any edge in the graph. In this paper, we study the hardness of EDPwC in undirected graphs. We show that for any constant $eps>0$ and any congestion $w=o(loglog M/logloglog M)$ there is no $log^{(1-eps)/(w+1)} M$-approximation algorithm for EDPwC, unless $NPsubseteq ZPTIME(n^{polylog n})$. For larger congestions $w
