INAPPROXIMABILITY OF EDGE-DISJOINT PATHS AND LOW CONGESTION ROUTING ON UNDIRECTED GRAPHS
01 January 2010
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
