Published Articles >> Table of Contents >> Abstract

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)   pp. 226-244
Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion
Matthew Andrews, Bell Laboratories, Lucent Technologies,
Julia Chuzhoy, CSAIL, MIT and Dept. of CIS, University of Pennsylvania,
Sanjeev Khanna, Dept. of CIS, University of Pennsylvania,
Lisa Zhang, Bell Laboratories, Lucent Technologies

Full Article Text:

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.41
Send link to a friend

Abstract
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 \subseteq ZPTIME(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.
Back to Top Additional Information
Citation:  Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang, "Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion," focs, pp. 226-244,  46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05),  2005