Hardness of the Undirected Edge-Disjoint Paths Problem

We show that there is no $log^{{1over 3}-ve} M$ approximation for the undirected Edge-Disjoint Paths problem unless $NP subseteq ZPTIME(n^{polylog~n})$, where $M$ is the size of the graph and $ve$ is any positive constant. This hardness result also applies to the undirected All-or-Nothing Multicommodity Flow problem and the undirected Node-Disjoint Paths problem.