In the undirected Edge-Disjoint Paths problem with Congestion
(EDPwC), we are given an undirected graph with V nodes, a set of
terminal pairs and an integer c. The objective is to route as many
terminal pairs as possible, subject to the constraint that at most
c demands can be routed through any edge in the graph. When c=1,
the problem is simply referred to as the Edge-Disjoint Paths (EDP)
problem. In this paper, we study the hardness of EDPwC in undirected
graphs.
Our main result is that for every \ve>0 there exists an
\alpha>0 such that for 1\le c\le \frac{\alpha\log\log V}{\log\log\log V}, it is hard to distinguish between instances
where we can route all terminal pairs on edge-disjoint paths, and
instances where we can route at most a 1/(\log V)^{\frac{1-\ve}{c+2}} fraction of the terminal pairs, even if we
allow congestion c. This implies a (\log V)^{\frac{1-\ve}{c+2}} hardness of approximation for EDPwC and an
\Omega(\log\log V/\log\log\log V) hardness of approximation for
the undirected congestion minimization problem. These results hold
assuming {\rm NP} \not\subseteq \cup_d {\rm ZPTIME}(2^{\log^d n}).
In the case that we do not require perfect completeness, i.e.\ we do
not require that all terminal pairs are routed for
``yes-instances'', we can obtain a slightly better inapproximability
ratio of (\log V)^{\frac{1-\ve}{c+1}}. Note that by setting c=1
this implies that the regular EDP problem is (\log V)^{\frac{1}{2}-\ve} hard to approximate.
Using standard reductions, our results extend to the node-disjoint
versions of these problems as well as to the directed setting. We
also show a (\log V)^{\frac{1-\ve}{c+1}} inapproximability ratio
for the All-or-Nothing Flow with Congestion (ANFwC) problem, a
relaxation of EDPwC, in which the flow unit routed between the
source-sink pairs does not have to follow a single path, so the
resulting flow is not necessarily integral.