### Logarithmic hardness of the undirected edge-disjoint paths problemLogarithmic hardness of the undirected edge-disjoint paths problem

Access Restriction
Subscribed

 Author Andrews, Matthew ♦ Zhang, Lisa Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2006 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Hardness of approximation ♦ Edge-disjoint paths ♦ Undirected graphs Abstract We show that there is no log⅓ ™ ϵ $\textit{M}$ approximation for the undirected Edge-Disjoint Paths problem unless $\textit{NP}$ ⊆ $ZPTIME(n^{polylog(n)}),$ where $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2006-09-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 53 Issue Number 5 Page Count 17 Starting Page 745 Ending Page 761

#### Open content in new tab

Source: ACM Digital Library