Edge Disjoint Paths Revisited

We study algorithms for the maximum edge disjoint paths problem in directed and undirected graphs obtaining improved approximation ratios. Our results lead us to believe that sparse graphs capture the difficulty of the EDP, and in particular we conjecture that the approximability threshold for directed EDP and the integrality gap of the LP relaxation are both Theta(square root of n).