Logarithmic hardness of the undirected edge-disjoint paths problem
Matthew Andrews, Lisa Zhang · Journal of the ACM · 2006
We show that there is no log ⅓ − ε M approximation for the undirected Edge-Disjoint Paths problem unless NP ⊆ ZPTIME ( n polylog( n ) ), where M is the size of the graph and ε 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.