Skip to main content

Logarithmic hardness of the undirected edge-disjoint paths problem

01 September 2006

New Image

We show that there is no log(1/3-epsilon) M approximation for the undirected Edge-Disjoint Paths problem unless NP subset of ZPTIME(n(polylog(n))), where M is the size of the graph and epsilon 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.