INAPPROXIMABILITY OF EDGE-DISJOINT PATHS AND LOW CONGESTION ROUTING ON UNDIRECTED GRAPHS

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 epsilon > 0 there exists an alpha > 0 such that for 1 = c = 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)(1-epsilon/c+2) fraction of the terminal pairs, even if we allow congestion c. This implies a (log V)(1-epsilon/c+2) hardness of approximation for EDPwC and an Omega(log log V/ logloglog V) hardness of approximation for the undirected congestion minimization problem. These results hold assuming NP not subset of U(d) ZPTIME(2(logdn)). 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)(1-epsilon/c+1). Note that by setting c = 1 this implies that the regular EDP problem is (log V)(1/2-epsilon) 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)(1-epsilon/c+1) inapproximability ratio for the All-or-Nothing Flow with Congestion (ANEwC) problem, a relaxation of ED-PwC, 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.