Inapproximability of Edge-Disjoint Paths and Low Congestion Routing on Undirected Graphs: A Random Hypergraph Instance Gives the Flow Relaxation an Integrality Gap of β₁/(4c) at Congestion c − 1Research Paper
In the edge-disjoint paths problem (EDP) one is given an undirected graph and a list of source–sink pairs, and asks how many pairs can be connected simultaneously by paths that share no edge. Its relaxation EDP with congestion (EDPwC) allows every edge to carry up to a fixed number of paths. Both are central problems of network routing and of approximation…