Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion

In the Edge-Disjoint Paths problem with Congestion (EDPwC), we are given a graph with n 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. We obtain an improved hardness result for EDP, and also show the first polylogarithmic integrality gaps and hardness of approximation results for EDPwC. Specifically, we prove that EDP is (\log ^{\frac{1}{2} - {\rm E}} n)-hard to approximate for any constant \varepsilon > 0, unless NP \subseteq ZPTIME(n^{poly\log n} ).We also show that for any congestion c = o(log log n/ log log log n), there is no (Log^{\frac{{1 - 5}}{{c + 1}}} n) approximation algorithm for EDPwC, unless NP\subseteqZPTIME(npolylog n).For larger congestion, where c = o(log log n/ log log log n) for some constant n, we obtain superconstant inapproximability ratios. All of our hardness results can be converted into integrality gaps for the multicommodity flow relaxation. We also present a separate elementary direct proof of this integrality gap result. Finally, we note that similar results can be obtained for the All-or-Nothing Flow (ANF) problem, a relaxation of EDP, in which the flow unit routed between the source-sink pairs does not have follow a single path, so the resulting flow is not necessarily integral. Using standard transformations, our results also extend to the node-disjoint versions of these problems as well as to the directed setting.