Shuheng Zhou
Electrical and Computer Engineering
CMU
Edge Disjoint Paths in Moderately Connected Graphs
ABSTRACT
We study the Edge
Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with
n nodes and a set T of pairs of terminals, connect as many
terminal pairs as possible using paths that are mutually edge disjoint. This
leads to a variety of classic NP-complete problems, for which approximability is
not well understood. For undirected EDP, the current hardness of approximation
result is W (log1/2-e
n).
We show a polylogarithmic approximation algorithm for the undirected EDP problem
in general graphs with a moderate restriction on graph connectivity; we require
the global minimum cut of G to be W
(log5 n). Previously, constant or polylogarithmic approximation
algorithms were known for trees with parallel edges, expanders, grids and
grid-like graphs, and most recently, even-degree planar graphs. These graphs
either have special structure (e.g., they exclude minors) or there are large
numbers of short disjoint paths. Our algorithm extends previous techniques in
that it applies to graphs with high diameters and asymptotically large minors.
This is joint work with Satish Rao.